uniolympiads English

IMC 2002, Ημέρα 2, Θέμα 2

Two hundred students participated in a mathematical contest. They had 66 problems to solve. It is known that each problem was correctly solved by at least 120120 participants. Prove that there must be two participants such that every problem was solved by at least one of these two students.

Πρωτότυπο από το επίσημο PDFTwo hundred students participated in a mathematical con- test. They had 6 problems to solve. It is known that each problem was correctly solved by at least 120 participants. Prove that there must be two participants such that every problem was solved by at least one of these two students.

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

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

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

Επίσημη λύση

Solution. For each pair of students, consider the set of those problems which was not solved by them. There exist (2002)=19900\binom{200}{2}=19900 sets; we have to prove that at least one set is empty.

For each problem, there are at most 80 students who did not solve it. From these students at most (802)=3160\binom{80}{2}=3160 pairs can be selected, so the problem can belong to at most 3160 sets. The 6 problems together can belong to at most 6⋅3160=189606\cdot3160=18960 sets.

Hence, at least 19900−18960=94019900-18960=940 sets must be empty.

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

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

Πώς πήγε;