Consider 2017 lines in the plane, which intersect pairwise at distinct points. Let be the set of these intersection points.
We want to assign a color to each point in such that any two points on the same line, whose segment connecting them contains no other point of , are of different colors.
What is the minimum number of colors needed to achieve such a coloring?
Solution
The sought minimum is , and with what follows, it will be quite evident that the result remains true for lines.
First, we note that, in the obtained configuration, there is at least one non-subdivided region that is a triangle. Indeed, three non-concurrent lines and two never parallel lines form a triangle. Now, any line that crosses a triangle divides it into two polygons, at least one of which is a triangle. Therefore, starting from three of the given lines and "adding" the other 2014 one by one, we are assured of the existence of such a triangular region in the final configuration. The three vertices of such a triangle must be of different colors, which implies that .
To conclude, we will construct an appropriate three-coloring. We start by noting that, since there are only a finite number of intersection points, we can choose an orthogonal coordinate system in which these points have distinct x-coordinates. We then number the points according to increasing x-coordinates (where ). For any , the point has at most four neighbors, and if it belongs to a segment joining two of its neighbors, only one of these two neighbors has an x-coordinate less than that of . This ensures that, for any , among the neighbors of , at most two have indices less than . We can then color the in the order of the numbering according to the following procedure: we color green and red. And, for any such that , if we assume that the points have been colored either green, red, or blue so that no two adjacent points are (yet) the same color, then, according to the previous remark, at most two neighbors of have already been colored, leaving one color free for .