uniolympiads English

IMC 2021, Ημέρα 1, Θέμα 2

Let nn and kk be fixed positive integers, and let aa be an arbitrary non-negative integer. Choose a random kk-element subset XX of {1,2,…,k+a}\{1, 2, \dots, k+a\} uniformly (i.e., all kk-element subsets are chosen with the same probability) and, independently of XX, choose a random nn-element subset YY of {1,…,k+n+a}\{1, \dots, k+n+a\} uniformly.

Prove that the probability

P(min⁡(Y)>max⁡(X))\mathsf{P}\big(\min(Y) > \max(X)\big)

does not depend on aa.

Πρωτότυπο από το επίσημο PDFLet n and k be fixed positive integers, and let a be an arbitrary non-negative integer. Choose a random k-element subset X of {1, 2, . . . , k + a} uniformly (i.e., all k-element subsets are chosen with the same probability) and, independently of X, choose a random n-element subset Y of {1, . . . , k + n + a} uniformly. Prove that the probability P( min(Y ) > max(X)) does not depend on a.

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

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

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

Επίσημη λύση

(proposed by Fedor Petrov, St. Petersburg State University)

Hint: The sets XX and YY with min⁡(Y)>max⁡(X)\min(Y) > \max(X) are uniquely determined by X∪YX \cup Y.

Solution 1. The number of choices for (X,Y)(X, Y) is (k+ak)⋅(n+k+an)\binom{k+a}{k}\cdot\binom{n+k+a}{n}.

The number of such choices with min⁡(Y)>max⁡(X)\min(Y) > \max(X) is equal to (n+k+an+k)\binom{n+k+a}{n+k} since this is the number of choices for the n+kn+k-element set X∪YX \cup Y and this union together with the condition min⁡(Y)>max⁡(X)\min(Y) > \max(X) determines XX and YY uniquely (note in particular that no elements of XX will be larger than k+ak+a). Hence the probability is

(n+k+an+k)(k+ak)⋅(n+k+an)=1(n+kk)\frac{\binom{n+k+a}{n+k}}{\binom{k+a}{k}\cdot\binom{n+k+a}{n}} = \frac{1}{\binom{n+k}{k}}
where the identity can be seen by expanding the binomial coefficients on both sides into factorials and canceling.

Since the right hand side is independent of aa, the claim follows.

Solution 2. Let ff be the increasing bijection from {1,2,…,k+a}\{1, 2, \ldots, k+a\} to {1,…,k+a+n}∖Y\{1, \ldots, k+a+n\} \smallsetminus Y. Note that min⁡(Y)>max⁡(X)\min(Y) > \max(X) if and only if min⁡(Y)>max⁡(f(X))\min(Y) > \max(f(X)).

Note that

{Zn:=Y,Zk:=f(X),Za:=f({1,2,…,k+a}∖X)}\{Z_n := Y, Z_k := f(X), Z_a := f(\{1, 2, \ldots, k+a\} \smallsetminus X)\}
is a random partition of
{1,…,n+k+a}=Zn⊔Zk⊔Za\{1, \ldots, n+k+a\} = Z_n \sqcup Z_k \sqcup Z_a
into an nn-subset, kk-subset, and aa-subset.

If an aa-subset ZaZ_a is fixed, the conditional probability that min⁡(Zk)>max⁡(Zn)\min(Z_k) > \max(Z_n) always equals 1/(n+kk)1/\binom{n+k}{k}. Therefore the total probability also equals 1/(n+kk)1/\binom{n+k}{k}.

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

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

Πώς πήγε;