Maths Olympiad Prep

Library / /127 of 155

Combinatorics Difficulty 6.9 National olympiad Prove it Saudi Arabia

In a school there are totally n>2n > 2 classes and not all of them have the same numbers of students. It is given that each class has one head student. The students in each class wear hats of the same color and different classes have different hat colors. One day all the students of the school stand in a circle facing toward the center, in an arbitrary order, to play a game. Every minute, each student puts his hat on the person standing next to him on the right. Show that at some moment, there are 2 head students wearing hats of the same color.

Solution

Suppose that there are mm students in total. We number the students standing in the circle by 1,2,3,,m1, 2, 3, \ldots, m, clockwise (starting with an arbitrary student). Denote by a1<a2<a3<<ana_{1} < a_{2} < a_{3} < \cdots < a_{n} the positions of the nn head students obtained in this numbering.

We consider an n×mn \times m table and fill numbers in its cells in the following way: For each 1in1 \leq i \leq n, in the ithi^{\text{th}} row, we start with aia_{i} (filling in the first cell of this row with aia_{i}) and continue with
ai+1, ai+2, , m, 1,2,,ai1 a_{i} + 1,\ a_{i} + 2,\ \ldots,\ m,\ 1, 2, \ldots, a_{i} - 1
to the right. We will focus on the hat colors of the students in the first column.

a1a_{1}a1+1a_{1} + 1a1+2a_{1} + 2\ldotsa11a_{1} - 1
a2a_{2}a2+1a_{2} + 1a2+2a_{2} + 2\ldotsa21a_{2} - 1
a3a_{3}a3+1a_{3} + 1a3+2a_{3} + 2\ldotsa31a_{3} - 1
ana_{n}an+1a_{n} + 1an+2a_{n} + 2\ldotsan1a_{n} - 1

At the first minute, each student in the first column wears his own hat.

At the second minute, based on the game rule, each student in the first column will wear the hat of the student in the same row but in the second column.

Similarly, at the kthk^{\text{th}} minute, each student in the first column will wear the hat of the student in the same row but in the kthk^{\text{th}} column, for each 1km1 \leq k \leq m.

Suppose, on the contrary, that we could never find 2 head students (in the first column) wearing hats of the same color. This would imply that at the beginning all the students in each column also wear hats of pairwise different colors, so they belong to distinct classes. Hence, the numbers of students of nn classes are the same, which is a contradiction to the hypothesis.

Therefore, at some moment, there are 2 head students wearing hats of the same color.

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 and solution reproduced as published; topic and difficulty added by this site.