Daniel chooses a positive integer $n$ and tells Ana. With this information, Ana chooses a positive integer $k$ and tells Daniel. Daniel draws $n$ circles on a piece of paper and chooses $k$ different points on the condition that each of them belongs to one of the circles he drew. Then he deletes the circles, and only the $k$ points marked are visible. From these points, Ana must reconstruct at least one of the circumferences that Daniel drew. Determine which is the lowest value of $k$ that allows Ana to achieve her goal regardless of how Daniel chose the $n$ circumferences and the $k$ points.
Problem
Source: Rioplatense Olympiad 2002 level 3 P6
Tags: combinatorics, game strategy, minimum, combinatorial geometry
07.09.2018 14:28
The answer is $k = 2n^2 + 1$. For a set of $k$ points in the plane, define a cover to be a set of $n$ circles such that each point belongs to at least one circle. Call a set of $k$ points good if it has at least one cover. We have to find the smallest $k$ such that for any good set of $k$ points, all of its covers have a circle in common. First we will show that $k \leq 2n^2 + 1$. Consider any good set $S$ of $2n^2 + 1$ points and take one of its covers. By PHP, there exists a circle $\mathcal{C}$ in the cover such that at least $\left\lceil \frac{2n^2 + 1}{n} \right\rceil = 2n + 1$ points from $S$ belong to $\mathcal{C}$. We claim that $\mathcal{C}$ belongs to each cover of $S$. Indeed, for any cover of $S$, by PHP at least $\left\lceil \frac{2n + 1}{n} \right\rceil = 3$ points from $S \cap \mathcal{C}$ belong to the same circle, thus $\mathcal{C}$ must be in the cover. Now we will show that $k \geq 2n^2 + 1$. It suffices to construct a set $S$ of $2n^2$ points having two disjoint covers. For $n = 1$ we can take any two points and for $n = 2$ just take $8$ points forming a $2 \times 4$ grid, so suppose that $n \geq 3$. Fix $n$ distinct numbers $l_1, l_2, \ldots, l_{n} \in \left(0, \sin\left(\frac{\pi (n - 2)}{2n}\right)\right)$ and take a regular $n$-gon of unit side length. For each vertex $V_i$ of the $n$-gon, draw the chords of the circle $\mathcal{C}_i$ centered at $V_i$ of radius $\frac{1}{2}$ that are perpendicular to the bisector of the angle at $V_i$, have lengths $l_1, l_2, \ldots, l_{n}$ and lie in the interior of the $n$-gon. Let $S$ be the set of endpoints of the $n^2$ drawn chords. Then the circles $\mathcal{C}_i$ form a cover of $S$. However, if we define $\Gamma_i$ to be the circle through the endpoints of the chords of length $l_i$ for each $1 \leq i \leq n$, then the circles $\Gamma_i$ also form a cover of $S$. Since these two covers are disjoint, we are done.