Fix a positive integer . Consider an -point set in the plane. An eligible set is a non-empty set of the form , where is a closed disc in the plane. In terms of , determine the smallest possible number of eligible subsets may contain.
Cristian Săvescu
Solution
The required minimum is .
We first show that an -point set in the plane contains at least eligible subsets. To this end, consider a line perpendicular to:
(1) No line through at least two points in ; and
(2) No tangent of a circle through at least three points in at a point in .
There are finitely many directions to avoid, so the choice of is possible.
By (1), projects injectively to to provide pairwise distinct points . Let be the (unique) point of whose orthogonal projection on is . By (2), any circle through an and tangent to passes through at most one other .
Fix an index and consider a circle through and tangent to , containing all points , inside; clearly, the all lie outside . By the preceding, shrinking homothetically from , the closed disc it bounds loses successively at most one . While shrinking, the disc first loses some , then some , and so on and so forth, to provide an index permutation of such that , are all eligible. This accounts for pairwise distinct eligible sets 'ending up' with ; that is, for all . In particular, for an index , the corresponding eligible sets are all different from each of the above.
Consequently, contains at least eligible sets, as stated.
We now exhibit an -point set in the plane with exactly eligible subsets. Let consist of collinear points, ordered along the line in question. The single-point segments , and the proper segments , are all eligible subsets of . Since the intersection of a line and a disc is either empty or a (possibly degenerate) segment, contains no other eligible subsets. Consequently, there are exactly eligible subsets in .