Problem A. 929. (March 2026)
A. 929. Let \(\displaystyle \mathcal{P}\) be a set of ten points in the plane. A subset \(\displaystyle \mathcal{Q}\subseteq \mathcal{P}\) is said to be isolable if there exists a closed disk of positive integer radius that contains all points of \(\displaystyle \mathcal{Q}\) but none of the points of \(\displaystyle \mathcal{P}\setminus\mathcal{Q}\). Prove that at least one third of the five-element subsets of \(\displaystyle \mathcal{P}\) are not isolable.
Proposed by Áron Bán-Szabó, Palaiseau
(7 pont)
Deadline expired on April 10, 2026.
Solution. First we prove a statement concerning set systems.
Let the set system \(\displaystyle \mathcal{F}\) consist of some subsets of the ground set \(\displaystyle H\) (that is, \(\displaystyle \mathcal{F}\subset 2^H\)). We call a subset \(\displaystyle G\) of \(\displaystyle H\) shattered if every subset of \(\displaystyle G\) can be obtained in the form \(\displaystyle G\cap F\), where \(\displaystyle F\in\mathcal{F}\). We claim that there are at least \(\displaystyle |\mathcal{F}|\) shattered subsets of \(\displaystyle H\) (where \(\displaystyle |\mathcal{F}|\) denotes the cardinality of \(\displaystyle \mathcal{F}\)).
We prove this statement by induction on the cardinality of \(\displaystyle \mathcal{F}\). The statement is true if \(\displaystyle |\mathcal{F}|=1\), since the empty set is shattered. Now suppose that \(\displaystyle |\mathcal{F}|\ge2\), and that the statement has already been proved for every set system with fewer than \(\displaystyle |\mathcal{F}|\) elements.
Since \(\displaystyle |\mathcal{F}|\ge2\), there exists an element \(\displaystyle h\in H\) such that there is an element of \(\displaystyle \mathcal{F}\) containing \(\displaystyle h\), and also one not containing \(\displaystyle h\). Let \(\displaystyle \mathcal{F}_1\) consist of those elements of \(\displaystyle \mathcal{F}\) that do not contain \(\displaystyle h\), and let \(\displaystyle \mathcal{F}_2\) consist of those that do contain \(\displaystyle h\). By the choice of \(\displaystyle h\), we have \(\displaystyle |\mathcal{F}_1|,|\mathcal{F}_2|<|\mathcal{F}|\), so the induction hypothesis can be applied to them, and since \(\displaystyle \mathcal{F}_1\) and \(\displaystyle \mathcal{F}_2\) form a disjoint union of \(\displaystyle \mathcal{F}\), we have
\(\displaystyle |\mathcal{F}|=|\mathcal{F}_1|+|\mathcal{F}_2|. \)
Now let \(\displaystyle \mathcal{G}_1\) consist of those subsets of \(\displaystyle H\) that are shattered by \(\displaystyle \mathcal{F}_1\), but cannot be shattered by \(\displaystyle \mathcal{F}_2\). Similarly, let \(\displaystyle \mathcal{G}_2\) consist of those subsets of \(\displaystyle H\) that are shattered by \(\displaystyle \mathcal{F}_2\), but cannot be shattered by \(\displaystyle \mathcal{F}_1\). Finally, let \(\displaystyle \mathcal{G}_3\) consist of those subsets of \(\displaystyle H\) that can be shattered both by \(\displaystyle \mathcal{F}_1\) and by \(\displaystyle \mathcal{F}_2\). By definition, it is clear that \(\displaystyle \mathcal{G}_1\), \(\displaystyle \mathcal{G}_2\), and \(\displaystyle \mathcal{G}_3\) are pairwise disjoint, and moreover \(\displaystyle \mathcal{G}_1\cup\mathcal{G}_3\) consists of the subsets of \(\displaystyle H\) shattered by \(\displaystyle \mathcal{F}_1\), so by the induction hypothesis
\(\displaystyle |\mathcal{G}_1|+|\mathcal{G}_3|\ge|\mathcal{F}_1| \)
and
\(\displaystyle |\mathcal{G}_2|+|\mathcal{G}_3|\ge|\mathcal{F}_2|. \)
Observe also that \(\displaystyle \mathcal{G}_1,\mathcal{G}_2,\mathcal{G}_3\subset H\setminus\{h\}\), since sets containing \(\displaystyle h\) cannot be shattered by \(\displaystyle \mathcal{F}_1\), because no element of \(\displaystyle \mathcal{F}_1\) contains \(\displaystyle h\), and similarly sets containing \(\displaystyle h\) cannot be shattered by \(\displaystyle \mathcal{F}_2\), because every element of \(\displaystyle \mathcal{F}_2\) contains \(\displaystyle h\). Finally, to complete the proof, it remains to observe that if \(\displaystyle G\in\mathcal{G}_3\), then \(\displaystyle G\cup\{h\}\) is also shattered by \(\displaystyle \mathcal{F}\), since the subsets not containing \(\displaystyle h\) can all be obtained using elements of \(\displaystyle \mathcal{F}_1\), while the subsets containing \(\displaystyle h\) can all be obtained using elements of \(\displaystyle \mathcal{F}_2\). Therefore the number of shattered sets is at least
\(\displaystyle |\mathcal{G}_1|+|\mathcal{G}_2|+2|\mathcal{G}_3| = (|\mathcal{G}_1|+|\mathcal{G}_3|) + (|\mathcal{G}_2|+|\mathcal{G}_3|) \ge |\mathcal{F}_1|+|\mathcal{F}_2| = |\mathcal{F}|. \)
Now let us turn to the solution of the problem. Let the set system \(\displaystyle \mathcal{F}\) consist of the separable subsets of our \(\displaystyle 10\)-point set. We must observe that shattered point sets can have at most three elements. To show this, it suffices to prove that every \(\displaystyle 4\)-element set has a subset that cannot be cut out by a separable subset, or equivalently by a circle, since a circle that cuts out a separable subset from the \(\displaystyle 10\)-point set cuts the subsets of the \(\displaystyle 10\)-point set in exactly the same way as the separable subset under consideration.
If the convex hull of the four points under consideration has at most \(\displaystyle 3\) vertices, then the set of vertices of the convex hull cannot be cut out, since the circle is a convex set, that is, if it contains the vertices of the convex hull, then it contains all the points.
If the convex hull of the four points has four vertices, that is, we have a convex quadrilateral \(\displaystyle ABCD\), then the sum of some pair of opposite angles is at least \(\displaystyle 180^\circ\). Without loss of generality, we may assume that
\(\displaystyle \angle ABC+\angle CDA\ge180^\circ. \)
Then the set \(\displaystyle \{A,C\}\) is not separable, because if there were a circle containing \(\displaystyle A\) and \(\displaystyle C\), but not \(\displaystyle B\) and \(\displaystyle D\), then let the line \(\displaystyle AC\) intersect the circle at the points \(\displaystyle A'\) and \(\displaystyle C'\), and let \(\displaystyle B'\) and \(\displaystyle D'\) be arbitrary points on the circle lying on the same side of the line \(\displaystyle AC\) as \(\displaystyle B\) and \(\displaystyle D\), respectively. Then
\(\displaystyle \angle ABC\le\angle A'BC'<\angle A'B'C', \)
and similarly one can show that
\(\displaystyle \angle CDA<\angle C'D'A', \)
which is a contradiction, since
\(\displaystyle \angle A'B'C'+\angle C'D'A'=180^\circ. \)
Thus the number of shattered sets is at most
\(\displaystyle \binom{10}{0}+\binom{10}{1}+\binom{10}{2}+\binom{10}{3}=176, \)
and therefore the number of separable sets is also at most this much. We need a slightly better bound, because
\(\displaystyle \frac23\binom{10}{5}=168, \)
however this is simple, since every singleton set is separable, so there are at most
\(\displaystyle 176-10=166 \)
separable sets of size five, and the proof is complete.
Statistics:
13 students sent a solution. 7 points: Aravin Peter, Bodor Mátyás, Bolla Donát Andor, Diaconescu Tashi, Forrai Boldizsár, Kis Ágoston, Morvai Várkony Albert, Sami El-Hajjar, Vödrös Dániel László (9 students). 6 points: Rajtik Sándor Barnabás (1 student). 0 points: 2 students. irregular: 1 script.
Problems in Mathematics of KöMaL, March 2026