A school has pupils, no two of whom are the same height. It also has a long bench on which the pupils can all sit in some order. An arrangement means some ordering of pupils on the bench. A swap means two pupils exchanging places while the other stay fixed. An arrangement is said to be unimodal if the heights increase in sequence up to the tallest member and then decrease in sequence. For this purpose, the increasing arrangement and the decreasing arrangement are also considered unimodal.
The pupils start the day sorted from shortest to tallest. They want to re-arrange themselves to the opposite order, from tallest to shortest, in a sequence of swaps, such that all intermediate arrangements are unimodal.
Can this be done?
Solution
We will prove the following stronger statement: For any positive integer and any two unimodal arrangements of pupils, there is a sequence of swaps leading from one of the arrangements to the other, via unimodal arrangements.
We show this by induction on . The result plainly holds when , as the sequence is both increasing and decreasing so no swap is required.
Suppose now that and inductively we may assume the claim for pupils. The shortest pupil must be at one of the two ends in a unimodal arrangement, so we can partition the set of all unimodal arrangements of pupils into two subsets: with the shortest pupil at the left end, and with the shortest pupil at the right end.
Inductively, I claim that is connected by swaps. Indeed, any two arrangements in can be connected by swaps involving the taller pupils, since any unimodal arrangement of the taller pupils remains unimodal when the shortest pupil is placed at the far left. By the same argument, is connected.
To complete the induction, we need to show that is connected to . It suffices to describe one arrangement from and one from which are connected by a swap. For example, numbering the pupils from (shortest) to (tallest), we obtain an arrangement in when we arrange the odd numbers in increasing order from the left, and the even numbers in increasing order from the right. Swapping pupils and gives an arrangement in .
This completes the inductive step and the result is proved.