Maths Olympiad Prep

Library / /3 of 4

Geometry Difficulty 8.7 Shortlist Prove it Romania

Fix a positive integer nn. Consider an nn-point set SS in the plane. An eligible set is a non-empty set of the form SDS \cap D, where DD is a closed disc in the plane. In terms of nn, determine the smallest possible number of eligible subsets SS may contain.
Cristian Săvescu

Solution

The required minimum is 12n(n+1)\frac{1}{2}n(n+1).

We first show that an nn-point set SS in the plane contains at least 12n(n+1)\frac{1}{2}n(n+1) eligible subsets. To this end, consider a line \ell perpendicular to:
(1) No line through at least two points in SS; and
(2) No tangent of a circle γ\gamma through at least three points in SS at a point in SγS \cap \gamma.
There are finitely many directions to avoid, so the choice of \ell is possible.
By (1), SS projects injectively to \ell to provide nn pairwise distinct points x1<<xnx'_1 < \cdots < x'_n. Let xkx_k be the (unique) point of SS whose orthogonal projection on \ell is xkx'_k. By (2), any circle through an xkx_k and tangent to xkxkx_kx'_k passes through at most one other xjx_j.

Fix an index kk and consider a circle ω\omega through xkx_k and tangent to xkxkx_kx'_k, containing all points xj,j<kx_j, j < k, inside; clearly, the xj,j>kx_j, j > k all lie outside ω\omega. By the preceding, shrinking ω\omega homothetically from xkx_k, the closed disc it bounds loses successively at most one xj,j<kx_j, j < k. While shrinking, the disc first loses some xj1,j1<kx_{j_1}, j_1 < k, then some xj2,j2j1,j2<kx_{j_2}, j_2 \neq j_1, j_2 < k, and so on and so forth, to provide an index permutation j1,j2,,jk=kj_1, j_2, \dots, j_k = k of 1,2,,k1, 2, \dots, k such that {xji,xji+1,,xjk},i=1,2,,k\{x_{j_i}, x_{j_{i+1}}, \dots, x_{j_k}\}, i = 1, 2, \dots, k, are all eligible. This accounts for kk pairwise distinct eligible sets 'ending up' with xkx_k; that is, xji<xjk=xkx'_{j_i} < x'_{j_k} = x'_k for all i<ki < k. In particular, for an index kkk' \neq k, the corresponding eligible sets are all different from each of the above.

Consequently, SS contains at least 1+2++n=12n(n+1)1 + 2 + \dots + n = \frac{1}{2}n(n+1) eligible sets, as stated.

We now exhibit an nn-point set SS in the plane with exactly 12n(n+1)\frac{1}{2}n(n+1) eligible subsets. Let SS consist of nn collinear points, ordered x1<<xnx_1 < \dots < x_n along the line in question. The nn single-point segments {xi},i=1,,n\{x_i\}, i = 1, \dots, n, and the 12n(n1)\frac{1}{2}n(n-1) proper segments {xi,xi+1,,xj},1i<jn\{x_i, x_{i+1}, \dots, x_j\}, 1 \le i < j \le n, are all eligible subsets of SS. Since the intersection of a line and a disc is either empty or a (possibly degenerate) segment, SS contains no other eligible subsets. Consequently, there are exactly n+12n(n1)=12n(n+1)n + \frac{1}{2}n(n-1) = \frac{1}{2}n(n+1) eligible subsets in SS.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.