Полуинвариант: как доказать завершение процесса
📐 Алгебра · 8 класс
Полуинвариант — величина, которая при разрешённых действиях меняется только в одну сторону или остаётся прежней. Если она строго изменяется при каждом ходе, её называют строгим пол
Полуинвариант — величина, которая при разрешённых действиях меняется только в одну сторону или остаётся прежней. Если она строго изменяется при каждом ходе, её называют строгим полуинвариантом. Метод помогает доказывать невозможность возвращения к прежней позиции и, при дополнительных условиях, завершение процесса.
Отличие от инварианта
Инвариант вообще не меняется. Например, при перестановке элементов списка сохраняется их сумма. Полуинвариант может уменьшаться: при сортировке полезно считать число неправильных пар. Выбирать величину нужно по действию задачи, а не по привычке всегда искать сумму.
Чтобы сделать вывод о завершении, одной монотонности мало. Последовательность 1,1/2,1/4,…строго убывает и ограничена снизу, но имеет бесконечно много членов. Надёжный школьный вариант — неотрицательная целочисленная величина, которая каждый ход уменьшается хотя бы на 1.
Пример: перестановка соседей
В ряду разных чисел разрешено менять местами соседние, если левое больше правого. Рассмотрим число инверсий — пар позиций i<j, у которых число слева больше числа справа. При обмене неправильных соседей количество инверсий уменьшается на 1. Остальные относительные порядки пар не меняются.
Число инверсий неотрицательно и целое. Поэтому бесконечно выполнять такие обмены нельзя. Когда обменов больше нет, каждая соседняя пара расположена по возрастанию, а значит весь ряд отсортирован. Мы доказали завершение не перечнем всех состояний, а одной подходящей мерой беспорядка.
Численный разбор
Для ряда 3,1,2 инверсии образуют пары 3–1 и 3–2: всего 2. Обмен первых соседей даёт 1,3,2, остаётся одна инверсия. Следующий обмен даёт 1,2,3, инверсий 0. Эта иллюстрация согласуется с доказательством, но не заменяет его: нужно объяснить изменение при любом разрешённом ходе.
Если разрешить менять любые два числа независимо от порядка, число инверсий уже не обязано только уменьшаться. Значит, та же величина перестанет быть полуинвариантом для новых правил. Метод всегда привязан к точно указанной операции.
Задания с ответами
1. Можно ли бесконечно вычитать 1 из неотрицательного целого, не выходя из этой области? Нет. 2. Доказывает ли убывание положительного действительного числа завершение? Не всегда: пример деления пополам показывает обратное. 3. Сколько инверсий в 2,1,3?Одна:2–1.
Для новой задачи запишите кандидат на величину, направление изменения и допустимые значения. Затем проверьте каждое разрешённое действие. Если хотя бы один ход увеличивает то, что должно уменьшаться, нужен другой полуинвариант или дополнительное ограничение. Точность правил здесь важнее красивого названия метода.
Как получить оценку числа ходов
Для ряда из n разных чисел количество инверсий не превышает n(n−1)/2: столько всего пар позиций. Значит, разрешённая сортировка завершится не более чем за это число обменов. Например, для четырёх чисел верхняя граница равна шести. Обратный ряд 4, 3, 2, 1 действительно имеет шесть инверсий. Это даёт больше, чем доказательство конечности: появляется количественная оценка. Если исходный ряд уже частично упорядочен, его реальное число инверсий меньше общей границы, и потребуется меньше обменов.
Связанные материалы
Перестановка элементов массива, Действия с целыми числами.
Источники и проверка
МЦНМО: Элементы математики в задачах, полуинварианты.