uniolympiads Ελληνικά

IMC 2013, Day 1, Problem 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?

Original from the official 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

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(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).

Transcribed from the official solutions, pages 1–2. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?