Question 12
There are $n$ students standing in a circle, one behind the other. The students have heights $h_1 \lt h_2 \lt \dots \lt h_n$. If a student with height $h_k$ is standing directly behind a student with height $h_{k-2}$ or less, the two students are permitted to switch places. Prove that it is not possible to make more than $\binom{n}{3}$ such switches before reaching a position in which no further switches are possible.
(This problem was suggested by Kiran Kedlaya, Travis Schedler, and David Speyer.)
(This problem was suggested by Kiran Kedlaya, Travis Schedler, and David Speyer.)