Maths Olympiad Prep

Library / /8 of 12

Combinatorics Difficulty 6.2 National Olympiad Prove it Mongolia

A class has 30 students and they sit in three groups of 10 students each. At the beginning of each month, the teacher swaps the students' seats. What is the minimum number of months needed in order for every pair of students to sit in the same group for at least a month?
(Proposed by Otgonbayar Uuye)

Solution

Let us say a pair of students is friends if they have sat in one group for at least a month.
Now we prove that four months is not enough. First note that for integers x0x \ge 0, y0y \ge 0, z0z \ge 0 such that x+y+z=10x + y + z = 10, we have
f(x,y,z)=(x2)+(y2)+(z2)12. f(x, y, z) = \binom{x}{2} + \binom{y}{2} + \binom{z}{2} \ge 12.
Indeed, by the arithmetic-quadratic mean inequality, we have
f(x,y,z)=12(x2+y2+z2)12(x+y+z)16(x+y+z)212(x+y+z)=11+23 f(x, y, z) = \frac{1}{2}(x^2 + y^2 + z^2) - \frac{1}{2}(x + y + z) \ge \frac{1}{6}(x + y + z)^2 - \frac{1}{2}(x + y + z) = 11 + \frac{2}{3}
and since f(x,y,z)f(x, y, z) is an integer, we have f(x,y,z)12f(x, y, z) \ge 12.

Let SS denote the set of students in the class. Then S=30|S| = 30. Let X,Y,ZX, Y, Z denote the groups of the first month. Here X,Y,ZSX, Y, Z \subseteq S and X=Y=Z=10|X| = |Y| = |Z| = 10. Suppose that for the next three months, the students sat in groups as follows:
T1,T2,T3T4,T5,T6T7,T8,T9. T_1, T_2, T_3 \quad T_4, T_5, T_6 \quad T_7, T_8, T_9.
For a group TST \subseteq S, each pair in XTX \cap T is already friends and similarly for YTY \cap T and ZTZ \cap T. Hence TT creates at most
(T2)(XT2)(YT2)(ZT2)4512=33 \binom{|T|}{2} - \binom{|X \cap T|}{2} - \binom{|Y \cap T|}{2} - \binom{|Z \cap T|}{2} \le 45 - 12 = 33
new friends. Here T=10|T| = 10 and (102)=45\binom{10}{2} = 45. It follows that in four months at most 345+933=4323 \cdot 45 + 9 \cdot 33 = 432 friends are created. There are (302)=435\binom{30}{2} = 435 pairs in total, thus four months is not enough to make every pair friends.

Five months is enough. Divide the students into six groups A,B,C,D,E,FA, B, C, D, E, F of five students each and sit as follows:
1ABCDEF2ACBEDF3ADBFCE4AEBDCF5AFBCDE \begin{vmatrix} 1 & AB & CD & EF \\ 2 & AC & BE & DF \\ 3 & AD & BF & CE \\ 4 & AE & BD & CF \\ 5 & AF & BC & DE \end{vmatrix}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.