Maths Olympiad Prep

Library / /110 of 120

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Croatia

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 NN (N3N \ge 3), 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 AA and BB (where BB is after AA in the clockwise direction) we put the symbol ♣ between them if BB is taller than AA and the symbol ♠ if BB is shorter than AA. In that way we obtain a sequence of NN 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 NN. Since the tallest person in the circle is not average the number of average people is certainly smaller than NN.
Let a1<a2<<aNa_1 < a_2 < \dots < a_N denote the heights of people. We will exhibit an example showing that for all k=1,,N/2k = 1, \dots, \lfloor N/2 \rfloor there exists a configuration of NN people in a circle such that exactly N2kN - 2k is average. More precisely, for a configuration where the people are ordered in a circle so that their heights are respectively
a1,aN,a2,aN1,,ak,aNk+1A,aNk,,ak+1G \underbrace{a_1, a_N, a_2, a_{N-1}, \dots, a_k, a_{N-k+1}}_{\text{A}}, \underbrace{a_{N-k}, \dots, a_{k+1}}_{\text{G}}
the first 2k2k people are not average and the remaining N2kN - 2k are average.
This shows that the number of average people can be any number strictly less than NN and having the same parity as NN.

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.