NMO Selection Tests for the Balkan and International Mathematical Olympiads - Second Selection Test

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

We first show that an $n$-point set $S$ in the plane contains at least $\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 $S$; and
(2) No tangent of a circle $\gamma$ through at least three points in $S$ at a point in $S \cap \gamma$.
There are finitely many directions to avoid, so the choice of $\ell$ is possible.
By (1), $S$ projects injectively to $\ell$ to provide $n$ pairwise distinct points $x'_1 < \cdots < x'_n$. Let $x_k$ be the (unique) point of $S$ whose orthogonal projection on $\ell$ is $x'_k$. By (2), any circle through an $x_k$ and tangent to $x_kx'_k$ passes through at most one other $x_j$.

Fix an index $k$ and consider a circle $\omega$ through $x_k$ and tangent to $x_kx'_k$, containing all points $x_j, j < k$, inside; clearly, the $x_j, j > k$ all lie outside $\omega$. By the preceding, shrinking $\omega$ homothetically from $x_k$, the closed disc it bounds loses successively at most one $x_j, j < k$. While shrinking, the disc first loses some $x_{j_1}, j_1 < k$, then some $x_{j_2}, j_2 \neq j_1, j_2 < k$, and so on and so forth, to provide an index permutation $j_1, j_2, \dots, j_k = k$ of $1, 2, \dots, k$ such that $\{x_{j_i}, x_{j_{i+1}}, \dots, x_{j_k}\}, i = 1, 2, \dots, k$, are all eligible. This accounts for $k$ pairwise distinct eligible sets 'ending up' with $x_k$; that is, $x'_{j_i} < x'_{j_k} = x'_k$ for all $i < k$. In particular, for an index $k' \neq k$, the corresponding eligible sets are all different from each of the above.

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

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