IMC 1997, Ημέρα 1, Θέμα 6
Suppose that is a family of finite subsets of and for any two sets we have .
a) Is it true that there is a finite subset of such that for any we have ?
b) Is the statement a) true if we suppose in addition that all of the members of have the same size?
Justify your answers.
Πρωτότυπο από το επίσημο PDF

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution. a) No. Consider , where , .
b) Yes. We will prove inductively a stronger statement:
Suppose , are two families of finite subsets of such that: 1) For every and we have ; 2) All the elements of have the same size , and elements of – size . (we shall write , ). Then there is a finite set such that for every and .
The problem b) follows if we take .
Proof of the statement: The statement is obvious for . Fix the numbers , and suppose the statement is proved for all pairs , with , . Fix , . For any subset , denote
Indeed, if we denote by the corresponding finite set, then the finite set will satisfy the statement for and . The proof for and .
If , it is trivial.
If , then any two sets , must meet outside . Then if we denote , , then and satisfy the conditions 1) and 2) above, with , , and the inductive assumption works.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 7–8. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.