Maths Olympiad Prep

Library / /431 of 462

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it Ireland

A school has 20202020 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 20182018 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 nn and any two unimodal arrangements of nn 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 nn. The result plainly holds when n=1n = 1, as the sequence is both increasing and decreasing so no swap is required.

Suppose now that n2n \ge 2 and inductively we may assume the claim for n1n-1 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 nn pupils into two subsets: L\mathcal{L} with the shortest pupil at the left end, and R\mathcal{R} with the shortest pupil at the right end.

Inductively, I claim that L\mathcal{L} is connected by swaps. Indeed, any two arrangements in L\mathcal{L} can be connected by swaps involving the taller n1n-1 pupils, since any unimodal arrangement of the n1n-1 taller pupils remains unimodal when the shortest pupil is placed at the far left. By the same argument, R\mathcal{R} is connected.

To complete the induction, we need to show that L\mathcal{L} is connected to R\mathcal{R}. It suffices to describe one arrangement from L\mathcal{L} and one from R\mathcal{R} which are connected by a swap. For example, numbering the pupils from 11 (shortest) to nn (tallest), we obtain an arrangement in L\mathcal{L} when we arrange the odd numbers in increasing order from the left, and the even numbers in increasing order from the right. Swapping pupils 11 and 22 gives an arrangement in R\mathcal{R}.

This completes the inductive step and the result is proved.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.