uniolympiads English

IMC 2013, Ημέρα 1, Θέμα 3

There are 2n2n students in a school (n∈Nn \in \mathbb{N}, n≥2n \ge 2). Each week nn students go on a trip. After several trips the following condition was fulfilled: every two students were together on at least one trip. What is the minimum number of trips needed for this to happen?

Πρωτότυπο από το επίσημο PDFThere are 2n students in a school (n ∈ N, n ≥ 2). Each week n students go on a trip. After several trips the following condition was fulfilled: every two students were together on at least one trip. What is the minimum number of trips needed for this to happen? n

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

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

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

Επίσημη λύση

(Proposed by Oleksandr Rybak, Kiev, Ukraine)

Solution. We prove that for any n≥2n \ge 2 the answer is 66.

First we show that less than 6 trips is not sufficient. In that case the total quantity of students in all trips would not exceed 5n5n. A student meets n−1n-1 other students in each trip, so he or she takes part on at least 3 excursions to meet all of his or her 2n−12n-1 schoolmates. Hence the total quantity of students during the trips is not less then 6n6n which is impossible.

Now let's build an example for 6 trips.

If nn is even, we may divide 2n2n students into equal groups AA, BB, CC, DD. Then we may organize the trips with groups (A,B)(A,B), (C,D)(C,D), (A,C)(A,C), (B,D)(B,D), (A,D)(A,D) and (B,C)(B,C), respectively.

If nn is odd and divisible by 3, we may divide all students into equal groups EE, FF, GG, HH, II, JJ. Then the members of trips may be the following: (E,F,G)(E,F,G), (E,F,H)(E,F,H), (G,H,I)(G,H,I), (G,H,J)(G,H,J), (E,I,J)(E,I,J), (F,I,J)(F,I,J).

In the remaining cases let n=2x+3yn = 2x+3y be, where xx and yy are natural numbers. Let's form the groups AA, BB, CC, DD of xx students each, and EE, FF, GG, HH, II, JJ of yy students each. Then we apply the previous cases and organize the following trips: (A,B,E,F,G)(A,B,E,F,G), (C,D,E,F,H)(C,D,E,F,H), (A,C,G,H,I)(A,C,G,H,I), (B,D,G,H,J)(B,D,G,H,J), (A,D,E,I,J)(A,D,E,I,J), (B,C,F,I,J)(B,C,F,I,J).

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

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

Πώς πήγε;