Fix a positive integer $n.{}$ Consider an $n{}$-point set $S{}$ in the plane. An eligible set is a non-empty set of the form $S\cap D,{}$ where $D$ is a closed disk in the plane. In terms of $n,$ determine the smallest possible number of eligible subsets $S{}$ may contain. Proposed by Cristi Săvescu
Problem
Source: Romania TST 2023 Day 2 P4
Tags: geometry, combinatorics, combinatorial geometry
07.04.2024 20:34
Maybe problem is near to trivialize by BAMO 2020/5 problem....
07.04.2024 21:31
Interesting We claim that there are at minimum $\binom{n+1}{2}$ such subsets. Claim: This can be constructed. Proof. A construction follows by taking all of $S$ on a line, which gives $\binom{n}{2}$ subsets when there are more than two elements in it, and $n$ more. This gives a total of $n + \binom{n}{2} = \binom{n+1}{2}$. $\blacksquare$ Claim: For a set $S$, we can generate $n+1$ distinct pairs of eligible sets $(A, A')$ where $A' = A \cup \{O\}$. Proof. Let one point $O$ of $S$ have minimal $x$ coordinate (rotate the plane until its uniquely minimal). Take a line that goes through $O$. By taking a sufficiently large circle, it can approximate a half plane bordering the line. First have this half plane containg on elements. Now rotate the line with pivot $O$. Suppose that when sorted by when they hit the ray, the elements can be ordered as sets $T_1, T_2, \dots$ where $T_i$ is a set of point(s) collinear with $O$. Then if $T_i = \{P\}$ has size one, we get a pair by considering when point $P$ is added to the set, and when the ray is perturbed such that $O$ isn't in the half plane. In the case where $T_i$ has size more than one, then we get $|T_i|$ pairs by considering half planes that contain the $k$th elements closest to $O$ for $1 \le k \le |T_i|$. We can once again guarentee such a perturbation to not have $O$ in the subsets. $\blacksquare$ Claim: This is minimal. Proof. We prove this inductively, the base case of $n = 2$ is obvious. Now suppose that we have a set $S$ of $n + 1$ points. Fix $O$ as before. Then $S \setminus \{O\}$ inductively has at least $\binom{n+1}{2}$ eligible sets. For each such eligible set, take a representation of it. This creates a matching from eligible sets on $S \setminus \{O\}$ to $S$ which agree on all elements but perhaps $O$. For each pair, then take the element of the pair which disagrees on $O$. This gives that $S$ has at least $\binom{n+1}{2} + n+1 = \binom{n+2}{2}$. $\blacksquare$
09.04.2024 19:30
This is my solution. The minimum is $\binom{n+1}{2}$ . We will initially show that for any initial configuration of $S$ we have at least $\binom{n+1}{2}$ eligible subsets. Claim : For every point in S there is a circle that passes through it and does not pass through the other $n-1$ points. Let $S={ A_1,A_2,\ldots,A_n }$.We will prove the claim for $A_1$. We consider $l$ a straight line that passes through $A_1$ and does not pass through the other n-1 points.We consider $O$ a point on $l$ such that $O$ is not on the perpendicular bisector of $A_1A_i$ for every i from 2 to n. Now the circle with the center $O$ that passes through $A_1$ respects the condition in the claim .So the claim is proved. Analogously, we will prove that for any pair of 2 points in $S$ there is a circle that passes through them and does not pass through the other $n-2$ points.So we have at least $n+\binom{n}{2}=\binom{n+1}{2}$ eligible subsets of $S$. Now we will build an example in which the minimum is reached. Thus we consider $n$ distinct collinear points .So the configuration reaches the minimum.