XIX Silk Road Mathematical Competition

Let's remind Helly's theorem: if in a finite set of convex sets of points on a plane each three intersect, then all of them intersect.

Let's prove that $n=9m$ satisfies the problem statement. Let $X$ be an arbitrary set of $9m$ different points on a plane, and $Y$ — the set of subsets of $X$ of size $6m+1$.

Suppose that there exist such $A,B,C\in Y$ that their intersection is empty. Let's enumerate all points in $X$ by numbers from $1$ to $9m$. Let's write down on a sheet of paper the numbers of points in $A$, then the numbers of points in $B$, and after that the numbers of points in $C$. We wrote $|A|+|B|+|C|=18m+3$ numbers in total. Since these sets do not intersect, then we couldn't write any number more than twice. Thus, we wrote no more than $2\cdot 9m=18m$ numbers — a contradiction. Therefore, any three elements of $Y$ intersect.

Since the convex hull of a set of points contains the set itself, then the convex hulls of any three elements of $Y$ intersect. According to Helly's theorem, the convex hulls of all elements of $Y$ share some common point $O$.

Let's prove the following lemma: if the convex hull of a finite set of points $Z$ contains some point $P$, then there exists such $W\subseteq Z$ that $|W|\le 3$ and the convex hull of $W$ contains $P$. By definition of convex hull, there exists a convex polygon with the set of vertices $V\subseteq Z$ (possibly, degenerate) that contains $P$. If $|V|\le 3$, then $V$ works as $W$. Otherwise, let's perform an arbitrary triangulation of the polygon with vertices in $V$. Point $P$ has to lie in at least one of the obtained triangles. The set of vertices of such triangle works as $W$.

Suppose we have a bag into which we can put non-empty subsets of $X$. Let's denote the following operation, which modifies $X$ and $Y$: take any $A\in Y$. Since the convex hull of $A$ contains $O$, then, according to the lemma, there exists such $B\subseteq A$ that $|B|\le 3$ and the convex hull of $B$ contains $O$. Let's put $B$ into our bag (obviously, $B$ is non-empty), delete elements of $B$ from $X$, and delete sets from $Y$ that contain element of $B$.

After one such operation the size of $X$ decreases by at most three, and $Y$ remains non-empty as long as $|X|\ge 6m+1$. Therefore, we can perform the operation at least $m$ times. Let's perform it exactly $m$ times. Distribute the remaining elements of $X$ randomly among the sets in the bag.

So, the sets in the bag constitute a partition of the initial set of points into $m$ non-empty sets and the convex hull of each of them contains point $O$, which is what we wanted.

---

Alternative solution.

Let's prove by induction on $m$ that any finite set of at least $4m^2$ different points on a plane can be partitioned into $m$ non-empty sets, convex hulls of which intersect. Obviously, the claim holds for $m=1$. Assume that it holds for $m=k-1$, where $k\ge 2$. Let's prove that it also holds for $m=k$. Let's consider an arbitrary finite set $X$ consisting of at least $4k^2$ different points on a plane. Let $Y$ be the subset of points of $X$ that lie on the border of the convex hull of $X$.

If $|Y|<4k$, then $|X\setminus Y|>4k^2-4k>4(k-1{)}^2$. By the induction hypothesis, $X\setminus Y$ can be partitioned into $k-1$ non-empty sets, convex hulls of which intersect. If we add $Y$ to these $k-1$ sets, then we would get $k$ sets, convex hulls of which intersect (since the convex hull of $Y$ contains all points from $X\setminus Y$).

If $|Y|\ge 4k$, then there are two cases.

If all points from $Y$ lie on the same line, then all points from $X$ lie on the same line. Let's draw a coordinate axis along this line and denote the points from $X$ by $A_1,A_2,\dots ,A_{|X|}$ in the order of increasing coordinates. Since $4k^2>2k$, then the following partition works: $$X=\{A_1,A_{|X|}\}\cup \{A_2,A_{|X|-1}\}\cup \cdots \cup \{A_{k-1},A_{|X|-k+2}\}\cup \{A_k,A_{k+1},\dots ,A_{|X|-k+1}\}$$

Otherwise points of $Y$ lie on the border of some non-degenerate convex polygon. Denote the points from $Y$ in clockwise order by $$A_1,A_2,\dots ,A_k,B_k,B_{k-1},\dots ,B_1,C_1,C_2,\dots ,C_k,D_k,D_{k-1},\dots ,D_1,E_1,E_2,\dots ,E_{|Y|-4k}.$$ Let $$Z=\{A_k,B_k,C_k,D_k,E_1,\dots ,E_{|Y|-4k}\}\cup (X\setminus Y).$$ Let's prove that the following partition works: $$X=\left(\bigcup _{i=1}^{k-1}\{A_i,B_i,C_i,D_i\}\right)\cup Z.$$ It is enough to prove the key assertion: convex hulls of $$\{A_1,B_1,C_1,D_1\},\{A_2,B_2,C_2,D_2\},\dots ,\{A_k,B_k,C_k,D_k\}$$ intersect. Denote the convex hull of a set of points $M$ by $f(M)$. Let $$T\in A_1{B}_1\cap A_k{D}_k,$$ $$H_i=f(\{A_1,A_2,\dots ,A_i,B_i,B_{i-1},\dots ,B_1,C_1,C_2,\dots ,C_i,D_i,D_{i-1},\dots ,D_1\})$$ and $$V_i=f(\{A_i,A_{i+1},\dots ,A_k,B_k,B_{k-1},\dots ,B_i,C_i,C_{i+1},\dots ,C_k,D_k,D_{k-1},\dots ,D_i\}).$$ Then for each $1\le i\le k$ holds $$T\in A_1{B}_1\subseteq H_i\text{ and }T\in A_k{D}_k\subseteq V_i.$$ Therefore, $$T\in \bigcap _{i=1}^k(H_i\cap V_i)=\bigcap _{i=1}^{k}f(\{A_i,B_i,C_i,D_i\}),$$ Q.E.D.