Exercise 16. Let $k \geqslant 1$ be an integer. What is the smallest integer $n$ such that, no matter how $n$ points are placed in the plane, it is possible to choose a subset $S$ consisting of $k$ of these points that satisfies "for every pair $P, Q$ of points in $S$, the distance between $P$ and $Q$ is less than or equal to 2" or "for every pair $\mathrm{P}, \mathrm{Q}$ of points in $\mathrm{S}$, the distance between $\mathrm{P}$ and $\mathrm{Q}$ is strictly greater than 1."
Solution to Exercise 16 Let's start by showing that $n=(k-1)^{2}+1$ is possible. For this, consider the disk of radius 1 centered at a point $P_{1}$ in the set. If there are at least $k$ points in this disk, we can take for $S$ these $k$ points (the distances between them are less than or equal to 2). Therefore, we can assume that there are at most $(k-1)$ points in the disk.

Now consider a disk of radius 1 centered at a $P_{2}$ in the set that is not in the previous disk. By the same argument, we can assume that there are at most $(k-1)$ points in this disk.

Continuing to choose points outside the previous disks, and since we exclude at most $(k-1)$ points at each step, we can construct $S=\{P_{1}, \ldots, P_{k}\}$ in such a way that the distances between these points are all strictly greater than 1.

To show that $n=(k-1)^{2}$ is not possible, we place at a very large distance from each other $k-1$ groups, where each group consists of $k-1$ points at a very small distance from each other.

Graders' Comments: This exercise was very well done by those who tackled it, with very varied methods: some used the same technique as the solution, others resorted to graph theory, for example.