Exercise 8. Patricia placed 2018 points in the plane, such that the distances between any two points are all distinct. She then colors each of her 2018 points, making sure that for each point $P$, the points $Q$ and $R$ placed closest and farthest from $P$ are the same color as $P$.

How many colors, at most, could Patricia have used?
Solution to Exercise 8 We will show that Patricia could have used a maximum of 504 colors. First, as soon as a color is used to color a vertex $v$, it is also used to color the closest and farthest vertices from $v$, i.e., at least 3 vertices.

Now suppose that at least two colors have been used to color only 3 vertices each. We call these vertices $A_{1}, A_{2}, A_{3}$ and $B_{1}, B_{2}, B_{3}$, respectively. Without loss of generality, we assume that $A_{1} A_{2} < A_{2} A_{3} < A_{3} A_{1}$ and $B_{1} B_{2} < B_{2} B_{3} < B_{3} B_{1}$. Then $A_{2}$ is the closest vertex to $A_{3}$ and $B_{3}$ is the farthest vertex from $B_{2}$, so $A_{2} A_{3} < B_{2} A_{3} < B_{2} B_{3}$. We would similarly show that $B_{2} B_{3} < A_{2} A_{3}$, leading to a contradiction. Therefore, our assumption was false, and at most one color has been used to color only 3 vertices.

If Patricia used $k$ colors, she has thus colored at least $4k - 1$ vertices. This shows that $4k - 1 \leq 2018$, hence

$$
k \leq \left\lfloor \frac{2018 + 1}{4} \right\rfloor = 504
$$

Conversely, here is a figure of a possible construction for 14 instead of 2018. We detail below the construction for 2018.

![](https://cdn.mathpix.com/cropped/2024_06_04_dba72b67df798c080479g-09.jpg?height=479&width=811&top_left_y=1208&top_left_x=649)

Patricia constructs a regular 1008-gon. She numbers its vertices clockwise from $A_{1}$ to $A_{1008}$, then slightly moves them so that the distances between points $A_{i}$ are all distinct: such perturbations can be chosen to be arbitrarily small. Next, near each point $A_{i}$, and still ensuring that the distances between points are all distinct, she places a point $B_{i}$. Finally, she places two points $C_{1}$ and $C_{2}$ near $A_{1}$ and $A_{2}$.

Then, for each vertex $X_{i}$, where $X \in \{A, B, C\}$, the closest vertex is one of the other vertices $X_{i}$, and the farthest vertex is one of the vertices $X_{504+i}$ (if $1 \leq i \leq 504$) or $X_{i-504}$ (if $505 \leq i \leq 1008$). Patricia thus uses colors numbered from 1 to 504, and paints the vertices $X_{k}$ and $X_{k+504}$ with color $k$. The first sentence of the paragraph shows that this coloring satisfies the conditions of the problem, and Patricia has therefore used 504 colors, which concludes the exercise.

Remark: As in Exercise 2, the argument used to show that at most 504 colors were available makes use of the minimax theorem: the largest of the minimal distances from a point to the other points is equal to the smallest of the maximal distances from a point to the other points. Here, this result was applied to the points $A_{2}, A_{3}, B_{2}$, and $B_{3}$.