Question 2
There are $n$ students standing in a circle, one behind the other.
The students have heights $h_1\lt h_2\lt \ldots \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.
Proposed by David Speyer (credit in the supplied third-party notes).
The students have heights $h_1\lt h_2\lt \ldots \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.
Proposed by David Speyer (credit in the supplied third-party notes).