Задача
COM-B2-M04-P011 Перестановки соседей
Числа \(1,2,\ldots,n\) стоят в некотором порядке. За один ход разрешается поменять местами две соседние числа, если левое больше правого. Докажите, что независимо от выбора ходов процесс закончится возрастающей последовательностью.
Следите за числом инверсий.
Инверсией назовём пару позиций \(i Если меняются соседние числа \(x>y\), то пара \((x,y)\) перестаёт быть инверсией. Отношения этих двух чисел со всеми остальными числами не меняют общего числа инверсий, потому что они соседние. Поэтому число инверсий уменьшается на \(1\). Оно не может уменьшаться бесконечно, значит, процесс завершится. В конце нет соседних чисел в неправильном порядке. Тогда вся последовательность возрастает.
Задача связывает экстремальный принцип с моноинвариантом.