uniolympiads English

IMC 2019, Ημέρα 2, Θέμα 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?

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;