Problem

Source: Pakistan TST (2) 2017. P2

Tags: combinatorics, algorithm



There are $n$ students in a circle, one behind the other, all facing clockwise. The students have heights $h_1 <h_2 < h_3 < \cdots < h_n$. If a student with height $h_k$ is standing directly behind a student with height $h_{k-2}$ or lesss, 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.