Задача
COM-B2-M05-P011 Сортировка соседними обменами
#11
★★★☆☆ Уровень 3 из 5
В строке стоят числа \(1,2,\ldots,n\) в произвольном порядке. Если соседние числа стоят в неправильном порядке, их разрешается поменять местами. Докажите, что процесс не может продолжаться бесконечно.
Используйте число инверсий.
Инверсией называется пара чисел, где большее стоит левее меньшего. Число инверсий — неотрицательное целое число.
Обмен соседней неправильной пары уменьшает число инверсий ровно на \(1\): эта пара перестаёт быть инверсией, а отношения этих двух чисел с остальными числами не меняют общего количества инверсий.
Значит, число инверсий строго убывает и не может убывать бесконечно. Процесс завершится.
Повторяет метод, но здесь акцент именно на моноинварианте.