Problem

Source: 2016 Saudi Arabia GMO TST level 4, III p3

Tags: Coloring, combinatorics



In a school there are totally $n > 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 put 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.