uniolympiads English

IMC 2024, Ημέρα 1, Θέμα 5

Let n>dn > d be positive integers. Choose nn independent, uniformly distributed random points x1,…,xnx_1, \dots, x_n in the unit ball B⊂RdB \subset \mathbb{R}^d centered at the origin. For a point p∈Bp \in B denote by f(p)f(p) the probability that the convex hull of x1,…,xnx_1, \dots, x_n contains pp. Prove that if p,q∈Bp, q \in B and the distance of pp from the origin is smaller than the distance of qq from the origin, then f(p)≥f(q)f(p) \ge f(q).

Πρωτότυπο από το επίσημο PDFLet n > d be positive integers. Choose n independent, uniformly distributed random points x 1 , . . . , x n in the unit ball B ⊂ R d centered at the origin. For a point p ∈ B denote by f (p) the probability that the convex hull of x 1 , . . . , x n contains p. Prove that if p, q ∈ B and the distance of p from the origin is smaller than the distance of q from the origin, then f (p) ≥ f (q). After the end of contest, the solutions and preliminary results will be posted at https://imc-math.org.uk/?year=2024&item=problems and https://imc-math.org.uk/?year=2024&item=results.

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

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

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

Επίσημη λύση

(proposed by Fedor Petrov, St Petersburg State University)

Solution. By radial symmetry of the distribution, f(p)f(p) depends only on ∣op∣|op| (the distance between oo and pp), so, we may assume that pp lies on the segment between oo and qq. For points x1,…,xnx_1, \dots, x_n and x∈Bx \in B denote by fx(x1,…,xn)f_x(x_1, \dots, x_n) the indicator function of the event "xx is in the convex hull of x1,…,xnx_1, \dots, x_n". The claim follows from the following deterministic inequality

∑fp(±x1,…,±xn)⩾∑fq(±x1,…,±xn),(1)\sum f_p(\pm x_1, \dots, \pm x_n) \geqslant \sum f_q(\pm x_1, \dots, \pm x_n), \tag{1}
where x1,…,xn∈Bx_1, \dots, x_n \in B are arbitrary points in general position and the summations are over all 2n2^n choices of signs (here oo is identified with the origin, that is, xx and −x-x are symmetric with respect to oo). Indeed, taking the expectation in (1) over independent random uniform x1,…,xnx_1, \dots, x_n, we get 2nf(p)⩾2nf(q)2^nf(p) \geqslant 2^nf(q). (To be specific, here "general position" means that for any point set A⊂{±x1,…,±xn,p,q}A \subset \{\pm x_1, \dots, \pm x_n, p, q\}, which does not contain simultaneosuly xix_i and −xi-x_i, is not contained in an (affine) (∣A∣−2)(|A| - 2)-dimensional plane. This holds with probability 1.)

To prove (1), we use the following formula for the characteristic function χP\chi_P of the convex polyhedron P⊂RdP \subset \mathbb{R}^d: if P1,…,PkP_1, \dots, P_k are all facets of PP, and QiQ_i is the convex hull of oo and PiP_i, then χP=∑±χQi\chi_P = \sum \pm\chi_{Q_i}, where the sign is plus if oo and PP are on the same side of PiP_i, and minus otherwise. Indeed, for every point pp in general position look how the ray opop intersects the boundary of PP and realize that for at most two summands the contribution of the RHS at point pp is non-zero, and the total contribution equals 1 when pp is inside PP and 0 (possibly as 0=1−10 = 1 - 1) otherwise. Use this formula for every polyhedron PP with nn vertices y1,…,yny_1, \dots, y_n, where each yiy_i is ±xi\pm x_i. These polyhedrons are simplicial (all facets are simplices) because of the general position condition. Sum up over all 2n2^n such PP, we get the expression of ∑PχP\sum_P \chi_P as a linear combination of χS\chi_S, where SS are simplices formed by oo and some dd points in {±x1,…,±xn}\{\pm x_1, \dots, \pm x_n\} (not containing xix_i and −xi-x_i simultaneously).

For proving (1), it suffices to verify that all coefficients of χS\chi_S in this linear combination are positive (since two sides of (1) are the values of the sum ∑PχP\sum_P \chi_P at pp and qq). Let's find a coefficient of χS\chi_S, where, say, SS is a simplex with vertices o,x1,…,xdo, x_1, \dots, x_d. The plane α\alpha through x1,…,xdx_1, \dots, x_d partitions Rd\mathbb{R}^d onto two parts H+H^+ (containing oo) and H−H^- (not containing oo). For every pair {xi,−xi}\{x_i, -x_i\} with i>di > d, either both points belong to H+H^+, or one belongs to H−H^- and another to H+H^+. χS\chi_S goes with the plus sign for PP with vertices x1,…,xdx_1, \dots, x_d and other vertices from H+H^+, and with the minus sign for PP with vertices x1,…,xdx_1, \dots, x_d and other vertices from H−H^-. It is immediate that there are at least as many pluses as minuses.

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

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

Πώς πήγε;