## Exercise 1

In the plane, we are given 2011 distinct points colored either blue or red.

(i) Suppose that for every blue point, the disk centered at this point with radius 1 contains exactly two red points. What is the maximum number of blue points possible?

(ii) Suppose that for every blue point, the circle centered at this point with radius 1 contains exactly two red points. What is the maximum number of blue points possible?
## Solution.

(i) If there is a blue point, there must be at least two red points, so there cannot be more than 2009 blue points.

Conversely, if we consider 2009 disks of radius 1 having a common interior that is non-empty, it suffices to mark two red points in this common part and to mark in blue the centers of these 2009 disks to obtain a configuration with 2009 blue points that satisfies the conditions of the problem.

The maximum sought is therefore 2009.

(ii) Consider a configuration of $r$ red points and $b$ blue points satisfying the conditions of the problem, with $r+b=2011$. As above, we have $r \geq 2$.

If $R_{1}$ and $R_{2}$ are two distinct red points, we denote by $n\left(R_{1}, R_{2}\right)$ the number of blue points that are centers of circles of radius 1 passing through $R_{1}$ and $R_{2}$.

Since every circle of radius 1 centered at a blue point passes through exactly two red points, this ensures that:

- every blue point is counted at least once in some $n\left(R_{1}, R_{2}\right)$,
- if $\left\{R_{1}, R_{2}\right\}$ and $\left\{R_{1}^{\prime}, R_{2}^{\prime}\right\}$ are two distinct pairs of red points, then the blue points counted in $n\left(R_{1}, R_{2}\right)$ are distinct from the blue points counted in $n\left(R_{1}^{\prime}, R_{2}^{\prime}\right)$.

Thus, each blue point is counted exactly once in some $n\left(R_{1}, R_{2}\right)$. Summing over the pairs of red points, we get

$$
\sum_{\left\{R_{1}, R_{2}\right\}} n\left(R_{1}, R_{2}\right)=b
$$

On the other hand, for any pair of points in the plane, there are at most two circles of radius 1 that pass through these two points, so we have $n\left(R_{1}, R_{2}\right) \leq 2$ for any pair $R_{1}, R_{2}$ of red points. Since there are $r(r-1) / 2$ pairs of red points, we then have:

$$
b=\sum_{\left\{R_{1}, R_{2}\right\}} n\left(R_{1}, R_{2}\right) \leq \sum_{\left\{R_{1}, R_{2}\right\}} 2=r(r-1)
$$

and thus $r(r-1) \geq 2011-r$, or equivalently $r^{2} \geq 2011$. It is easy to deduce that $r \geq 45$, and therefore that $b \leq 1966$.

Conversely, consider 45 red points, all located on the same segment of length 1. Any two of these red points always belong to two circles of radius 1. We draw only 1966 of these circles (we could draw $1980 = 45 \times 44$), and we mark in blue the centers of these circles. It is easy to verify that we thus obtain a configuration with 2011 colored points that satisfies the conditions of the problem.

The maximum sought is therefore 1966.