$2n+1$ segments on a line

Question

$2n+1$ segments are marked on a line. Each of these segments intersects at least $n$ other segments. Prove that one of these segments intersects all other segments.

Answer 1

Describe the line segments as intervals on the real line and list them in order of appearance from left to right. Denote the $i$th line segment by $L_i=(s_i,f_i)$. Set up a graph $G$ where each vertex corresponds to a line segment, and two vertices are adjacent if their corresponding line segments intersect. Let $A$ be the adjacency matrix of $G$. $A$ is clearly symmetric. Notice also that $L_i \cap L_k \Leftrightarrow s_i <s_k <f_i$. For $i<j<k$, if $L_i\cap L_k$ we have that $s_i <s_j<s_k$ because of the ordering but also $s_i<s_j<f_i \Rightarrow L_i \cap L_j$. This gives a second property for $A$, i.e:

$\text{If } a_{ik} =1 \text{ then } a_{ij}=1 \text{ for all } j \text{ such that } i\le j\le k \tag{1}$

Now we just need to prove that $A$ has a row that is all $1$'s. We can prove this by trying to construct a matrix with the given properties that does not satisfy this condition.
Introduce a set $I_j=\{ m \in \mathbb N : a_{j,m} = 1\}$ and let $M_j = \max I_j$. It is obvious that for all $j$, $n+1\le M_j$, otherwise $|I_j| \le n$. This implies $a_{j,n+1} =1$ for all $j$. Take $a_{i,j}$ such that $1\le i,j \le n+1$. If $i=j$ then $a_{i,j}=1$, if $i<j$, then $a_{i,j}=1$ by $(1)$, if $j<i$, then $a_{j,i}=1$ by $(1)$ again, and $a_{i,j}=1$ since $A$ is symmetric.
If for $j$ between $1$ and $n+1$ we had that $a_{j,2n+1}=1$ then the whole $j$th row would be all $1$'s by property $(1)$ and by what we just proved. Therefore, $a_{j,2n+1} = 0$ and thus $a_{2n+1,j} = 0$ for all $j\in \{1,...,n+1\}$. But this is impossible, since then $|I_{2n+1}|\le n$.

Answer 2

Let us define each line segment by intervals of the form $[a, b]$. We will be referring a as left end and b as right end.

Let us consider $X$ = union of $n$ left most (by picking left ends) line segments and $Y$ = union of $n$ right most (by picking right ends) line segments.

Now in $X$, rightmost left end will be left of the leftmost right end otherwise there will be a line in $X$ which will have less than $n-1$ intersections. This implies each segment in $X$ pairwise intersecting with each other which corresponds to $n – 1$ intersection of each line segments with in these $n$ line segments in $X$.

Similarly in $Y$, leftmost right end will be right of the rightmost left end otherwise there will be a line in $Y$ which will have less than $n – 1$ intersections. This implies each segment in $Y$ is also pairwise intersecting with each other which corresponds to $n – 1$ intersection of each line segments with in these $n$ line segments in $Y$.

Now if there is any common line segment between $X$ and $Y$, then this line segments intersect with all line segments of $X$ as well as all line segments of $Y$. So this line segment intersects with all other line segments and we are done.

If there is no common line segment between $X$ and $Y$, then $X$ and $Y$ will be disjoint sets each containing $n$ line segments. There will be one more line segment(as there are total $2n + 1$ line segments). This line segment must intersect with each line segment contained in $X$ as we need n intersection on each line segment. Similarly this line segment must intersect with each line segment contained in $Y$. So this is the line segment which intersects with all other line segments and we are done.