, 2010

(By Kiran Kedlaya). Let $h_i$ also denote the student with height $h_i$. We prove that for $1 \le i < j \le n$, $h_j$ can switch with $h_i$ at most $j - i - 1$ times. We proceed by induction on $j - i$, the base case $j - i = 1$ being evident because $h_i$ is not allowed to switch with $h_{i-1}$.

For the inductive step, note that $h_i, h_{j-1}, h_j$ can be positioned on the circle either in this order or in the order $h_i, h_j, h_{j-1}$. Since $h_{j-1}$ and $h_j$ cannot switch, the only way to change the relative order of these three students is for $h_i$ to switch with either $h_{j-1}$ or $h_j$. Consequently, any two switches of $h_i$ with $h_j$ must be separated by a switch of $h_i$ with $h_{j-1}$. Since there are at most $j - i - 2$ of the latter, there are at most $j - i - 1$ of the former.

The total number of switches is thus at most
$$\begin{aligned} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} (j-i-1) &= \sum_{i=1}^{n-1} \sum_{j=0}^{n-i-1} j \\ &= \sum_{i=1}^{n-1} \binom{n-i}{2} \\ &= \sum_{i=1}^{n-1} \left[ \binom{n-i+1}{3} - \binom{n-i}{3} \right] \\ &= \binom{n}{3}. \end{aligned}$$

(By Warut Suksompong). For $i = 1, 2, \dots, n-1$, let $s_i$ be the number of students $h_j$ with $j < i$ such that $h_{i+1}, h_j$, and $h_i$ appear in that order on the circle. Note that $s_i \le i-1$ for all $i$. Now we take a look what happens when two students switch places.

* If $h_n$ is involved in the switch, $s_{n-1}$ decreases by 1, while all the other $s_i$'s remain the same.
* Otherwise, suppose $h_a$ and $h_b$ are switched. Then, we have $a+1 < b < n$, so $s_{b-1}$ decreases by 1, while $s_b$ increases by 1. All other $s_i$'s remain the same.

Therefore, we see that the quantity $M = \sum_{i=1}^{n-1} (n-i)s_i$ decreases by exactly 1 after every switch. The number of switches until no more are possible is therefore at most the initial value of $M$. Because $s_i \le i-1$ for $1 \le i \le n-1$, this value is at most $\sum_{i=1}^{n-1} (n-i)(i-1) = \binom{n}{3}$.

Note. With this solution, it is also easy to see that the number of switches until no more are possible depends only on the original ordering.