IMC 2022, Ημέρα 2, Θέμα 8
Let be integers, and let be a circle. Let blue points and red points be chosen uniformly and independently at random on the circle . Denote by the intersection of the convex hull of the red points and the convex hull of the blue points. Let be the number of vertices of the convex polygon (in particular, when is empty). Find the expected value of .
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Fedor Petrov, St. Petersburg)
Hint:
Solution 1. We prove that
Let be blue points. Fix . Enumerate our points starting from a blue point counterclockwise as . Denote the minimal index for which the point is blue as . So, is a side of the convex hull of blue points. Denote by the following random variable:
Define analogously random variables for the red points. Clearly,
We proceed with computing the expectation of each and . Note that if and only if all red points lie on the side of the line . This happens either if , i.e., the point is blue (which happens with probability ), or if , points are red, and points are blue (which happens with probability , since all subsets of size of have equal probabilities to correspond to the indices of red points between ). Thus the expectation of equals . Analogously, the expectation of equals . It remains to use and linearity of expectation.
Solution 2. Let be the colours of the points, scanned counterclockwise from a fixed point on the circle. We consider the sequence as cyclic (so is also adjacent to ). There are two cases: Either (i) all red points appear contiguously, followed by all blue points contiguously, or (ii) the red and blue points alternate at least twice. It can be seen that in the second case, is exactly equal to the number of colour changes in the sequence: For example, if is red and is blue, then the intersection of the red chord from to the next red point with the blue chord from to the previous blue point is a vertex of , and every vertex is of this form. Case (i) is exceptional, as we have two colour changes, but , so it is 2 less than the number of changes in that case.
Now observe that the distribution of is purely combinatorial: Each of the distributions of colours is equally likely (for example, because we can generate the distribution by first choosing all points on the circle, and then assigning colours uniformly). In particular the probability that is a colour change is exactly , and by lineraity of expectation, the total expected number of color changes (including ) is times this, i.e. .
To get the expected value of , we must subtract from the above 2 times the probability of case (i). Exactly of the distributions belong to case (i), so we must subtract , as claimed.
Solution 3. Let be the blue points and be the red points. For every pair of blue points , , , we evaluate the probability that contains a side of (it obviously does not depend on the choice of and ). By denote the analogous probability for the red points. Then by linearity of expectation we have .
We proceed with finding . Without loss of generality , . Let the length of the circle be 1, and the length of arc (counterclockwise from to ) be . Then is uniformly distributed on . Then contains a side of if
(i) all blue points are on the same side of , but
(ii) the red points are not on the same side of .
The probability of (i) is . The probability of is .
Thus, using Beta function value for positive integers
Next,
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 4–5. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.