Инвариант — величина или свойство, которое сохраняется при каждом разрешённом действии. Но искать его необязательно среди самых заметных чисел. Иногда сумма записей меняется, а неизменной остаётся сумма вместе с ещё одним показателем. Рассмотрим самостоятельное учебное упражнение для подготовки к математической олимпиаде; официальному соревнованию оно не приписывается.
Слияние двух записей
На листе записаны числа 2, 5, 8 и 10. За один ход разрешается выбрать любые две записи a и b, стереть их и вместо них записать a + b + 1. Продолжаем, пока не останется одна запись. Какое число получится и зависит ли оно от выбора пар? Выбирать нужно именно две записи: если значения совпадут, они всё равно остаются отдельными участниками операции.
Попробуем сначала соединить 2 и 5. Вместо них появляется 8, и остаются записи 8, 8, 10. Затем две восьмёрки дают 17, а числа 17 и 10 — итог 28. Можно начать иначе: соединить 8 и 10, получить 19; затем соединить 5 и 19, получить 25; последняя пара 2 и 25 снова даёт 28.
От совпадения к общей проверке
Две цепочки помогают предположить, что ответ постоянен. Они ещё не объясняют поведение всех остальных выборов. Вместо продолжения перебора разберём один произвольный ход, не привязываясь к тому, какие именно две записи выбраны.
Обозначим сумму всех записей буквой S, а их количество — буквой n. Стирание a и b уменьшает сумму на a + b; новая запись увеличивает её на a + b + 1. Поэтому после любого хода сумма становится S + 1. Число записей одновременно уменьшается на единицу и становится n − 1.
Теперь сложим два показателя. После хода получаем (S + 1) + (n − 1) = S + n. Значит, величина S + n не меняется. Это общий расчёт: значения a и b из него исчезли, поэтому он охватывает любой разрешённый выбор пары.
Доведём рассуждение до ответа
Вначале S = 25 и n = 4, то есть инвариант равен 29. После завершения остаётся одна запись, её значение обозначим x. Тогда сумма тоже равна x, а количество равно единице. Следовательно, x + 1 = 29, откуда x = 28.
Остаётся проверить, что процесс действительно завершается: каждый ход уменьшает количество записей ровно на одну. Из четырёх записей после трёх ходов получается одна; раньше остановиться по условию нельзя. Инвариант объясняет значение результата, а уменьшение количества — число ходов. Это две разные части решения.
Для самопроверки начните с четырёх единиц. Исходная сумма равна 4, количество — 4, поэтому последняя запись должна равняться 7. Если в ручной цепочке вышло другое число, проверьте прибавление единицы при каждом слиянии.
В учебнике MIT «Mathematics for Computer Science», раздел 5.4.3 общий принцип связывает проверку начального состояния с сохранением свойства при каждом переходе. Наши числа и правило слияния составлены для этой статьи. При изменении правила инвариант нужно вывести заново: похожая запись операции не гарантирует прежнего ответа.
