Prove that for any natural number $ m $ there exists a natural number $ n $ such that any $ n $ distinct points on the plane can be partitioned into $ m $ non-empty sets whose convex hulls have a common point. The convex hull of a finite set $ X $ of points on the plane is the set of points lying inside or on the boundary of at least one convex polygon with vertices in $ X $, including degenerate ones, that is, the segment and the point are considered convex polygons. No three vertices of a convex polygon are collinear. The polygon contains its border.
Problem
Source: SRMC 2020 P4 - Silk Road
Tags: combinatorial geometry, combinatorics, Convex hull
18.08.2020 23:25
We try to prove our statement by induction on m. the base Case is $m=1$ which is clear. assume now the condition holds for $m$, that is: if we have n points on the plane we can partition them into m non-empty sets whose convex hulls have a common point.now consider $T>10n$ I will prove if we have $T$ points on the plane we can partision them into $m+1$ sets whose convex hulls have a common point.I will divide this in to 2 cases Case 1:If we have more than n points in the convex hull of this $T$ points. we can partition the points in the convex hull in to m sets whose convex hulls have a common point and put the points on the convex hull in to the $m+1_{th}$ set . its clear that this $m+1$ sets are non-empty and their convex hulls have a common point. Case 2:assume $A_1A_2 \dots A_s$ be the convex hull of this $T $points $(s>9n)$. now consider the triangles $A_1A_2A_3, A_4A_5A_6, \dots $there are $n$ triangle from this trangles which they dont have any other points in them. Because we have less than n points in the convex hull .Now concider the middle vertical of this triangles(those that dont have any points in them) say $B_1B_2 \dots B_l$ were $l>n$ so we can partition this l points into $m$ sets whose convex hulls have a common point and put all of the other points in the $m+1_{th}$ set. now you can easily see this $m+1$ convex hulls have a common point and we are done by induction on $m$.
05.03.2023 17:23
We try to solve this by using induction for $m$. Define a sequense$a_m$as follows: $a_2=5, a_n=3a_{n-1}$. I claim that there is a solotion when $n \ge a_m$. First: $m=2$. We know that among $5$ distinct points, there must be $4$ points forming a convex quadrilateral. Let it be $ABCD$, and $E$ is the fifth point. Separate the points $\{A,C,E\}$ and $\{B,D\}$ gives a successful example. Assume that $n=a_m$ works when $\le n$. When it comes to $n+1$, we consider the following two situations: P1. There are less than $2a_n$ vertices on the convex hull. This means there are at least $a_n$ points srtictly lie inside the convex hull. We let the points on the convex hull be an independent subset then we divide the points inside the convex hull into $n$ subsets using the inductive hypothesis. This obviously works. P2. There are not less than $2a_n$ vertices on the convex hull. We just need to divide the points on the convex hull into $n+1$ sets. First label the points on the convex hull clockwise $A_1,A_2, \dots, A_{2a_n}$. We set a subset $A_1,A_3, \dots , A_{2a_n-1}$ and divide the other $a_n$ points using the inductive hypothesis. Just see if this doesn't work, the points that the $n$ sets (even labelled ones) have in common($X$) must lies outside the convex hull formed by $1,3, \dots , 2a_n-1$. WLOG the point lies outside $A_1A_3$. Then notice that there is a subset that doesn't have points in $A_1, A_2, A_3$. So $X$ lies outside the convex hull of that subset ,too. Contradiction.
Attachments:

20.07.2023 18:03
We try to prove our statement by induction on m. the base Case is $m=1$ which is clear. assume now the condition holds for $m$, that is: if we have n points on the plane we can partition them into m non-empty sets whose convex hulls have a common point.now consider $T>7n$ I will prove if we have $T$ points on the plane we can partision them into $m+1$ sets whose convex hulls have a common point.I will divide this in to 2 cases Case 1:If we have more than n points in the convex hull of this $T$ points. we can partition the points in the convex hull in to m sets whose convex hulls have a common point and put the points on the convex hull in to the $m+1_{th}$ set . its clear that this $m+1$ sets are non-empty and their convex hulls have a common point. Case 2:assume $A_1A_2 \dots A_s$ be the convex hull of this $T $points $(s>9n)$. now consider the triangles $A_1A_2A_3, A_4A_5A_6, \dots $there are $n$ triangle from this trangles which they dont have any other points in them. Because we have less than n points in the convex hull .Now concider the middle vertical of this triangles(those that dont have any points in them) say $B_1B_2 \dots B_l$ were $l>n$ so we can partition this $l$ points into $m$ sets whose convex hulls have a common point and put all of the other points in the $m+1_{th}$ set. now you can easily see this $m+1$ convex hulls have a common point and we are done by induction on $m$. Comments: We can find that most vertices are on the convex hulls by induction.
18.06.2024 19:34
See Tverberg's theorem.
07.07.2024 15:52
2019-TST-21 proved $n=3m$ is enough.