Maths Olympiad Prep

Library / /3 of 4

Geometry Difficulty 6.9 National olympiad Prove it Silk Road Mathematics Competition

Prove that for any positive integer mm there exists a positive integer nn, such that any nn different points on a plane can be partitioned into mm non-empty sets, convex hulls of which would share a common point.

Convex hull of a finite set XX of points on a plane is a set of points that lie inside or on the border of at least one convex polygon with vertices in XX, including degenerate ones, i.e. a segment and a point are considered to be convex polygons. No three vertices of a convex polygon are collinear. A polygon contains its border.

Solutions — 2

Solution 1

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=9mn = 9m satisfies the problem statement. Let XX be an arbitrary set of 9m9m different points on a plane, and YY — the set of subsets of XX of size 6m+16m + 1.

Suppose that there exist such A,B,CYA, B, C \in Y that their intersection is empty. Let's enumerate all points in XX by numbers from 11 to 9m9m. Let's write down on a sheet of paper the numbers of points in AA, then the numbers of points in BB, and after that the numbers of points in CC. We wrote A+B+C=18m+3|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 29m=18m2 \cdot 9m = 18m numbers — a contradiction. Therefore, any three elements of YY intersect.

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

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

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

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

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

Solution 2

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

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

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

If all points from YY lie on the same line, then all points from XX lie on the same line. Let's draw a coordinate axis along this line and denote the points from XX by A1,A2,,AXA_1, A_2, \dots, A_{|X|} in the order of increasing coordinates. Since 4k2>2k4k^2 > 2k, then the following partition works:
X={A1,AX}{A2,AX1}{Ak1,AXk+2}{Ak,Ak+1,,AXk+1} X = \{A_1, A_{|X|}\} \cup \{A_2, A_{|X|-1}\} \cup \dots \cup \{A_{k-1}, A_{|X|-k+2}\} \cup \{A_k, A_{k+1}, \dots, A_{|X|-k+1}\}

Otherwise points of YY lie on the border of some non-degenerate convex polygon. Denote the points from YY in clockwise order by
A1,A2,,Ak,Bk,Bk1,,B1,C1,C2,,Ck,Dk,Dk1,,D1,E1,E2,,EY4k. 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={Ak,Bk,Ck,Dk,E1,,EY4k}(XY). 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=(i=1k1{Ai,Bi,Ci,Di})Z. 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
{A1,B1,C1,D1},{A2,B2,C2,D2},,{Ak,Bk,Ck,Dk} \{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 MM by f(M)f(M). Let
TA1B1AkDk, T \in A_1B_1 \cap A_kD_k,
Hi=f({A1,A2,,Ai,Bi,Bi1,,B1,C1,C2,,Ci,Di,Di1,,D1}) 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
Vi=f({Ai,Ai+1,,Ak,Bk,Bk1,,Bi,Ci,Ci+1,,Ck,Dk,Dk1,,Di}). 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 1ik1 \le i \le k holds
TA1B1Hi and TAkDkVi. T \in A_1 B_1 \subseteq H_i \text{ and } T \in A_k D_k \subseteq V_i.
Therefore,
Ti=1k(HiVi)=i=1kf({Ai,Bi,Ci,Di}), 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.