uniolympiads Ελληνικά

IMC 2019, Day 2, Problem 10

20192019 points are chosen at random, independently, and distributed uniformly in the unit disc {(x,y)∈R2:x2+y2≤1}\{(x, y) \in \mathbb{R}^2 : x^2 + y^2 \le 1\}. Let CC be the convex hull of the chosen points. Which probability is larger: that CC is a polygon with three vertices, or a polygon with four vertices?

Original from the official PDF2019 points are chosen at random, independently, and distributed uniformly in the unit disc {(x, y) ∈ R 2 : x 2 + y 2 ≤ 1} . Let C be the convex hull of the chosen points. Which probability is larger: that C is a polygon with three vertices, or a polygon with four vertices? Problem 10.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Proposed by Fedor Petrov, St. Petersburg State University

Solution. We will show that the quadrilateral has larger probability.

Let D={(x,y)∈R2 ⁣:x2+y2≤1}\mathcal{D} = \{(x, y) \in \mathbb{R}^2 \colon x^2 + y^2 \le 1\}. Denote the random points by X1,…,X2019X_1, \ldots, X_{2019} and let

p=P(C is a triangle with vertices X1,X2,X3),q=P(C is a convex quadrilateral with vertices X1,X2,X3,X4).\begin{aligned} p &= P\big(C \text{ is a triangle with vertices } X_1, X_2, X_3\big), \\ q &= P\big(C \text{ is a convex quadrilateral with vertices } X_1, X_2, X_3, X_4\big). \end{aligned}

By symmetry we have P(C is a triangle)=(20193)pP\big(C \text{ is a triangle}\big) = \binom{2019}{3}p, P(C is a quadrilateral)=(20194)qP\big(C \text{ is a quadrilateral}\big) = \binom{2019}{4}q and we need to prove that (20194)q>(20193)p\binom{2019}{4}q > \binom{2019}{3}p, or equivalently p<20164q=504qp < \frac{2016}{4}q = 504q.

Note that pp is the average over X1,X2,X3X_1, X_2, X_3 of the following expression:

u(X1,X2,X3)=P(X4∈△X1X2X3)⋅P(X5,X6,…,X2019∈△X1X2X3),u(X_1, X_2, X_3) = P\big(X_4 \in \triangle X_1X_2X_3\big)\cdot P\big(X_5, X_6, \ldots, X_{2019} \in \triangle X_1X_2X_3\big),
and qq is not less than the average over X1,X2,X3X_1, X_2, X_3 of
v(X1,X2,X3)=P(X1,X2,X3,X4 form a convex quad.)⋅P(X5,X6,…,X2019∈△X1X2X3)).v(X_1, X_2, X_3) = P\big(X_1, X_2, X_3, X_4 \text{ form a convex quad.}\big)\cdot P\big(X_5, X_6, \ldots, X_{2019} \in \triangle X_1X_2X_3)\big).

Thus it suffices to prove that u(X1,X2,X3)≤500v(X1,X2,X3)u(X_1, X_2, X_3) \le 500v(X_1, X_2, X_3) for all X1,X2,X3X_1, X_2, X_3. It reads as area(△X1X2X3)≤500area(Ω)\mathrm{area}(\triangle X_1X_2X_3) \le 500\mathrm{area}(\Omega), where Ω={Y:X1,X2,X3,Y form a convex quadrilateral}\Omega = \{Y : X_1, X_2, X_3, Y \text{ form a convex quadrilateral}\}.

Assume the contrary, i.e., area(△X1X2X3)>500area(Ω)\mathrm{area}(\triangle X_1X_2X_3) > 500\mathrm{area}(\Omega).

Let the lines X1X2X_1X_2, X1X3X_1X_3, X2X3X_2X_3 meet the boundary of D\mathcal{D} at A1,A2,A3,B1,B2,B3A_1, A_2, A_3, B_1, B_2, B_3; these lines divide D\mathcal{D} into 7 regions as shown in the picture; Ω=D4∪D5∪D6\Omega = \mathcal{D}_4 \cup \mathcal{D}_5 \cup \mathcal{D}_6.

[Figure in the original PDF.]

By our indirect assumption,

area(D4)+area(D5)+area(D6)=area(Ω)<1500area(D0)<1500area(D)=π500.\mathrm{area}(\mathcal{D}_4) + \mathrm{area}(\mathcal{D}_5) + \mathrm{area}(\mathcal{D}_6) = \mathrm{area}(\Omega) < \frac{1}{500}\mathrm{area}(\mathcal{D}_0) < \frac{1}{500}\mathrm{area}(\mathcal{D}) = \frac{\pi}{500}.

From △X1X3B3⊂Ω\triangle X_1X_3B_3 \subset \Omega we get X3B3/X3X2=area(△X1X3B3)/area(△X1X2X3)<1/500X_3B_3/X_3X_2 = \mathrm{area}(\triangle X_1X_3B_3)/\mathrm{area}(\triangle X_1X_2X_3) < 1/500, so X3B3<1500X2X3<1250X_3B_3 < \frac{1}{500}X_2X_3 < \frac{1}{250}. Similarly, the lengths segments A1X1,B1X1,A2X2,B2X2,A3X2A_1X_1, B_1X_1, A_2X_2, B_2X_2, A_3X_2 are less than 1250\frac{1}{250}.

The regions D1,D2,D3\mathcal{D}_1, \mathcal{D}_2, \mathcal{D}_3 can be covered by disks with radius 1250\frac{1}{250}, so

area(D1)+area(D2)+area(D3)<3⋅π2502.\mathrm{area}(\mathcal{D}_1) + \mathrm{area}(\mathcal{D}_2) + \mathrm{area}(\mathcal{D}_3) < 3\cdot\frac{\pi}{250^2}.

Finally, it is well-known that the area of any triangle inside the unit disk is at most 334\frac{3\sqrt{3}}{4}, so

area(D0)≤334.\mathrm{area}(\mathcal{D}_0) \le \frac{3\sqrt{3}}{4}.

But then

∑i=06area(Di)<334+3⋅π2502+π500<area(D),\sum_{i=0}^{6}\mathrm{area}(\mathcal{D}_i) < \frac{3\sqrt{3}}{4} + 3\cdot\frac{\pi}{250^2} + \frac{\pi}{500} < \mathrm{area}(\mathcal{D}),
contradiction.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?