A group of people of different height decided to dance the Hungarian traditional dance at the opening ceremony of MEMO 2013 in Veszprém. We say that a person is average if he is taller than one of her neighbours and shorter than the other. (People stand in a circle and every person has exactly two neighbours.)
If the number of people is (), determine all possible numbers of average people. (Belarus 2012)
Solution
We first observe how the height of people changes as we go around the circle in the clockwise direction. For every pair of neighbours and (where is after in the clockwise direction) we put the symbol ♣ between them if is taller than and the symbol ♠ if is shorter than . In that way we obtain a sequence of symbols ♣ or ♠.
A person is average if and only if the symbol before that person is equal to the symbol after that person. Hence the number of people who are not average is equal to the number of alternations of the symbols ♣ and ♠. The number of changes from the symbol ♣ to ♠ is equal to the number of changes from ♠ to ♣. So the number of people who are not average is even.
From this we conclude that the number of average people is of the same parity as . Since the tallest person in the circle is not average the number of average people is certainly smaller than .
Let denote the heights of people. We will exhibit an example showing that for all there exists a configuration of people in a circle such that exactly is average. More precisely, for a configuration where the people are ordered in a circle so that their heights are respectively
the first people are not average and the remaining are average.
This shows that the number of average people can be any number strictly less than and having the same parity as .