IMC 2016, Ημέρα 1, Θέμα 4
Let be positive integers, and let be a family of finite sets with the following properties:
(i) contains at least distinct sets containing exactly elements;
(ii) for any two sets , their union also belongs to .
Prove that contains at least three sets with at least elements.
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
(Proposed by Fedor Petrov, St. Petersburg State University)
Solution 1. If then we have at least two distinct sets in the family with exactly elements and their union, so the statement is true. From now on we assume that .
Fix sets of size in , call them 'generators'. Let be the union of the generators. Since has at least subsets of size , we have .
Call an element 'appropriate' if belongs to at most generators. Then there exist at least generators not containing . Their union contains at least elements, and the union does not contain .
Now we claim that among any elements of , there exists an appropriate element. Consider all pairs such that is a generator and . Every generator has exactly elements, so the number of such pairs is at most . If some is not appropriate then is contained in at least generators; if none of was appropriate then we wold have at least pairs. But , so this is not possible; at least one of must be appropriate.
Since , the set contains some appropriate element . Let be the union of all generators not containing . Then and . Now take an appropriate element from and let be the union of all generators not containing . Then , so we have three sets, , and in with at least elements: because and , and is different from and because but .
Solution 2. We proceed by induction on , so we can assume that the statement of the problem is known for smaller values of . By contradiction, assume that has less than sets with at least elements, that is the number of such sets is , or . We can assume without loss of generality that consists of exactly distinct sets of size and all their possible unions. Denote the sets of size by .
Consider a maximal set such that has size less than , . This means that adding any for makes the size at least , . First, let's prove that such exist. Otherwise, all the sets are contained in . But there are only distinct -element subsets of , this is a contradiction. So there is at least one such that . Consider all possible sets that can be obtained as for . Their size is at least , so their number can be or . If there are two of them, say and then or , for otherwise the union of and would be different from both and , so we would have three sets , and of size at least . We see that in any case there must exist such that for all . Consider sets for . Their sizes are equal to . Their number is at least
The above argument allows us to decrease all the way to , so it remains to check the statement for . The assumption says that we have at least sets of size . This is impossible, because there is only one empty set. Thus the statement trivially holds for .
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 3. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.