Problem:
There are students standing in a circle, one behind the other. The students have heights . If a student with height is standing directly behind a student with height or less, the two students are permitted to switch places. Prove that it is not possible to make more than such switches before reaching a position in which no further switches are possible.
Solution:
Solution from Kiran Kedlaya: Let also denote the student with height . We prove that for can switch with at most times. We proceed by induction on , the base case being evident because is not allowed to switch with .
For the inductive step, note that can be positioned on the circle either in this order or in the order . Since and cannot switch, the only way to change the relative order of these three students is for to switch with either or . Consequently, any two switches of with must be separated by a switch of with . Since there are at most of the latter, there are at most of the former.
The total number of switches is thus at most
Note: One can also ask to prove that the number of switches before no more are possible depends only on the original ordering, or to find all initial positions for which switches are possible (the only one is when the students are sorted in increasing order).
Alternative Solution from Warut Suksompong: For , let be the number of students with height no more than standing (possibly not directly) behind the student with height and (possibly not directly) in front of the one with height . Note that for all .
Now we take a look what happens when two students switch places.
If the student with height is involved in the switch, decreases by 1 , while all the other 's remain the same.
\item Otherwise, suppose the students with heights and are switched, with , then decreases by 1 , while increases by 1 . All the other 's remain the same.
Since for all , the maximal number of switches is no more than the number of switches in the case where initially for all . In that case, the number of switches is .
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.
This problem was proposed by Kiran Kedlaya jointly with Travis Schedler and David Speyer.
The problems on this page are the property of the MAA's American Mathematics Competitions