Problem
COM-B2-M04-P011 Swapping Neighbours
The numbers \(1,2,\ldots,n\) are arranged in some order. In one move, one may swap two neighbouring numbers if the left one is larger than the right one. Prove that no matter how the moves are chosen, the process ends with the increasing sequence.
Track the number of inversions.
Call a pair of positions \(i When neighbouring numbers \(x>y\) are swapped, the pair \((x,y)\) stops being an inversion. Their relations with all other numbers do not change the total number of inversions because the two numbers were adjacent. Thus the number of inversions decreases by \(1\). It cannot decrease forever, so the process stops. At the end there is no neighbouring pair in the wrong order. Therefore the whole sequence is increasing.
This problem connects the extremal principle with a monovariant.