IMC 2021, Ημέρα 1, Θέμα 2
Let and be fixed positive integers, and let be an arbitrary non-negative integer. Choose a random -element subset of uniformly (i.e., all -element subsets are chosen with the same probability) and, independently of , choose a random -element subset of uniformly.
Prove that the probability
does not depend on .
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(proposed by Fedor Petrov, St. Petersburg State University)
Hint: The sets and with are uniquely determined by .
Solution 1. The number of choices for is .
The number of such choices with is equal to since this is the number of choices for the -element set and this union together with the condition determines and uniquely (note in particular that no elements of will be larger than ). Hence the probability is
Since the right hand side is independent of , the claim follows.
Solution 2. Let be the increasing bijection from to . Note that if and only if .
Note that
If an -subset is fixed, the conditional probability that always equals . Therefore the total probability also equals .
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 2–3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.