Maths Olympiad Prep

Library / /192 of 520

Combinatorics Difficulty 6.2 National olympiad Find the answer

Consider 2017 lines in the plane, which intersect pairwise at distinct points. Let EE be the set of these intersection points.
We want to assign a color to each point in EE such that any two points on the same line, whose segment connecting them contains no other point of EE, are of different colors.
What is the minimum number of colors needed to achieve such a coloring?

A number or a short expression. Spacing and $ signs are ignored.

Solution

The sought minimum mm is m=3m=3, and with what follows, it will be quite evident that the result remains true for n3n \geq 3 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 m3m \geq 3.
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 M1,M2,,MkM_{1}, M_{2}, \ldots, M_{k} according to increasing x-coordinates (where k=2017×20162k=\frac{2017 \times 2016}{2}). For any ii, the point MiM_{i} 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 MiM_{i}. This ensures that, for any iki \leq k, among the neighbors of MiM_{i}, at most two have indices less than ii. We can then color the MiM_{i} in the order of the numbering according to the following procedure: we color M1M_{1} green and M2M_{2} red. And, for any ii such that 2ik12 \leq i \leq k-1, if we assume that the points M1,M2,,MiM_{1}, M_{2}, \ldots, M_{i} 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 Mi+1M_{i+1} have already been colored, leaving one color free for Mi+1M_{i+1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.