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 , , such that , we have
Indeed, by the arithmetic-quadratic mean inequality, we have
and since is an integer, we have .
Let denote the set of students in the class. Then . Let denote the groups of the first month. Here and . Suppose that for the next three months, the students sat in groups as follows:
For a group , each pair in is already friends and similarly for and . Hence creates at most
new friends. Here and . It follows that in four months at most friends are created. There are pairs in total, thus four months is not enough to make every pair friends.
Five months is enough. Divide the students into six groups of five students each and sit as follows: