18th Turkish Mathematical Olympiad

The answer is $4019$. We will show that the answer is $2n-1$ for a $n$-gon if $n\ge 5$. Let $A$ be an intersecting set with $|A|\ge n$. Since the number of vertices in $A$ is not greater than the number of line segments in $A$, $A$ contains a cycle. Let $PQ$ and $QR$ be two line segments in this cycle. Every line segment in the cycle, except $XP$ and $RY$, intersects both $PQ$ and $QR$ at their interior points. We conclude that the cycle contains an odd number of line segments and none of the vertices on the cycle lies inside the angle $\angle PQR$. Hence there is a positive integer $k$ and there are vertices $P_1,P_2,\dots ,P_{2k+1}$ in the order they lie on the polygon such that the cycle consists of the line segments $P_i{P}_{i+k},P_i{P}_{i+k+1}$ for $1\le i\le 2k+1$. (Indices are considered modulo $n$.) Let us denote this collection by $A^{\ast }$. Since $A$ is intersecting, the only other line segments in $A$ can be of the form $X{P}_i$ where $X$ is a vertex of the polygon lying inside the angle $\angle P_{i+k+1}{P}_i{P}_{i+k}$. Since $|A|\ge n$ all such line segments must belong to $A$. Let us denote the collection of these line segments by $A^{\mathcal{C}}$. Therefore if $A$ is an intersecting set with $|A|\ge n$, then $|A|=n$ and $A=A_{(P_1,P_2,\dots ,P_{2k+1})}=A^{\ast }\bigsqcup A^{\mathcal{C}}$ where $A^{\ast }$ and $A^{\mathcal{C}}$ are as described above.

Next we will show that if $A$ and $B$ are intersecting sets with $|A|=n=|B|$, then $A$ and $B$ cannot be disjoint. Assume they are. Let $Q_1{Q}_2,Q_2{Q}_3,\dots ,Q_{m-1}{Q}_m,Q_m{Q}_1$ be a cycle such that the line segments $Q_i{Q}_{i+1}$ belong to, say, $A$ for $i$ odd and $B$ for $i$ even (where $Q_{m+1}=Q_1$). Such a cycle exists as every vertex of the polygon is an endpoint of at least one line segment in $A$ and one in $B$. Since $A$ and $B$ are intersecting, all $Q_i{Q}_{i+1}$ intersect $Q_1{Q}_2$ for $i$ odd and $Q_2{Q}_3$ for $i$ even. Therefore all $Q_i$ with $i$ even lie on or the opposite side of $Q_1{Q}_2$ with respect to $Q_3$ and all $Q_i$ with $i$ odd lie on or the opposite side of $Q_2{Q}_3$ with respect to $Q_1$. In particular, $m$ is odd and $Q_1$ is a vertex of $A^{\ast }$. Then $Q_3$ lies on or the opposite side of $Q_m{Q}_1$ with respect to $Q_2$, and $Q_{m-1}$ lies on or the opposite side of $Q_1{Q}_2$ with respect to $Q_m$. Let $X{Q}_1$ be a line segment belonging to $B$. Since $X{Q}_1$ must intersect both $Q_2{Q}_3$ and $Q_{m-1}{Q}_m$, which belong to $B$, $X$ must lie between $Q_2$ and $Q_m$ on the polygon. But then $X{Q}_1$ also belongs to $A^c$ and hence to $A$, a contradiction.

Finally, if $P$, $Q$, $R$, $S$, $T$ are five consecutive vertices on the polygon, then $A_{(P,Q,R)}\cup A_{(R,S,T)}$ consists of $2n-1$ line segments.