Let's prove by induction on m that any finite set of at least 4m2 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≥2. Let's prove that it also holds for m=k. Let's consider an arbitrary finite set X consisting of at least 4k2 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∖Y∣>4k2−4k>4(k−1)2. By the induction hypothesis, X∖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∖Y).
If ∣Y∣≥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 A1,A2,…,A∣X∣ in the order of increasing coordinates. Since 4k2>2k, then the following partition works:
X={A1,A∣X∣}∪{A2,A∣X∣−1}∪⋯∪{Ak−1,A∣X∣−k+2}∪{Ak,Ak+1,…,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
A1,A2,…,Ak,Bk,Bk−1,…,B1,C1,C2,…,Ck,Dk,Dk−1,…,D1,E1,E2,…,E∣Y∣−4k.
Let
Z={Ak,Bk,Ck,Dk,E1,…,E∣Y∣−4k}∪(X∖Y).
Let's prove that the following partition works:
X=(i=1⋃k−1{Ai,Bi,Ci,Di})∪Z.
It is enough to prove the key assertion: convex hulls of
{A1,B1,C1,D1},{A2,B2,C2,D2},…,{Ak,Bk,Ck,Dk}
intersect. Denote the convex hull of a set of points M by f(M). Let
T∈A1B1∩AkDk,
Hi=f({A1,A2,…,Ai,Bi,Bi−1,…,B1,C1,C2,…,Ci,Di,Di−1,…,D1})
and
Vi=f({Ai,Ai+1,…,Ak,Bk,Bk−1,…,Bi,Ci,Ci+1,…,Ck,Dk,Dk−1,…,Di}).
Then for each 1≤i≤k holds
T∈A1B1⊆Hi and T∈AkDk⊆Vi.
Therefore,
T∈i=1⋂k(Hi∩Vi)=i=1⋂kf({Ai,Bi,Ci,Di}),
Q.E.D.