Problem: There are $n$ students standing in a circle, one behind the other.
The students have heights $h_1<h_2<\dots <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.

Solution: The main claim is the following observation,
which is most motivated in the situation $j-i = 2$.
\begin{claim*}
  The students with heights $h_i$ and $h_j$
  switch at most $|j-i|-1$ times.
\end{claim*}
\begin{proof}
  By induction on $d = |j-i|$, assuming $j > i$.
  For $d = 1$ there is nothing to prove.

  For $d \ge 2$, look at only students $h_j$, $h_{i+1}$
  and $h_{i}$ ignoring all other students.
  After $h_j$ and $h_i$ switch the first time,
  the relative ordering of the students must be
  $h_i \to h_j \to h_{i+1}$.
  Thereafter $h_j$ must always switch with $h_{i+1}$
  before switching with $h_i$,
  so the inductive hypothesis applies to give the bound
  $1 + j - (i+1) - 1 = j-i - 1$.
\end{proof}
Hence, the number of switches is at most
\[ \sum_{1 \le i < j \le n} \left( |j-i| - 1 \right) = \binom n3. \]