75th NMO Selection Tests

Lemma. Given 5 points in the plane, no three collinear, it is impossible to color the 10 segments determined by them with only 2 colors so that any two segments of the same color intersect.

First, we show that any 4 points determine a monochromatic triangle. The 4 points form either a convex or concave quadrilateral. Label the points $A$, $B$, $C$, $D$ so that $AB$, $CD$ and $AD$, $BC$ are pairs of non-intersecting segments. Without loss of generality, assume $AB$, $BC$ are red and $CD$, $AD$ are blue. The color of $AC$ (red or blue) then determines a monochromatic triangle.

Next, we show that there cannot be two distinct monochromatic triangles of the same color. Suppose there are two red triangles, one being $ABC$. Then any red segment must have an endpoint in $\{A,B,C\}$. Without loss of generality, assume the other red triangle is $ABD$. The coloring rule then implies that the pairs of segments $AD$, $BC$ and $AC$, $BD$ intersect, which is impossible.

Therefore, since two distinct monochromatic triangles of the same color cannot exist, the 5 monochromatic triangles determined by the 5 subsets of 4 points would have to be identical, i.e., contain the same triple of points for every 4-point subset, which is a contradiction.

Step 1. Consider a regular 10-gon and color its vertices alternately with two colors: red and blue. Let $v$ be a red vertex. Consider the 9 segments containing $v$, together with the diagonal formed by the two adjacent blue vertices. Any two of these segments intersect (either in their interior or at endpoints), so they can be colored with the same color. Thus, we can cover all segments except the diagonals of the pentagon formed by the blue vertices using 5 colors. Since those diagonals intersect pairwise, they require a sixth color.

Step 2. We prove that $k\ge 6$ using the lemma. Let $A$ be a set of points as in the statement, and consider a line $l_0$ not parallel to any of the 45 segments determined by the points of $A$. Ordering the distances of the 10 points from $l_0$, we construct a line $l$ parallel to $l_0$ so that there are 5 points on each side of $l$. Look at the segments formed by the 5 points on the same side of $l$. By the lemma, at least 3 colors are needed to color these segments so that any two segments of the same color intersect. On the other hand, no segment on one side of $l$ can have the same color as a segment on the other side since they do not intersect. Thus, at least 6 colors are needed to color all 45 segments, completing the proof.