Замените множество состояний одним признаком
Пусть лежат девять карточек белой стороной вверх. За ход разрешено перевернуть любые две разные карточки. Можно ли получить девять чёрных сторон? Состояний много, и попытки перебирать ходы быстро запутывают. Вместо полного рисунка будем следить за числом чёрных карточек. Само число меняется, но нас интересует только его чётность. Это пример полезного упрощения: сохранить ровно ту информацию, которая может отделить начальное состояние от желаемого.
Проверьте все типы одного хода
Если перевернуть две белые карточки, чёрных станет на две больше. Если две чёрные, на две меньше. Если одну белую и одну чёрную, количество не изменится. Других случаев нет. Во всех трёх случаях чётность числа чёрных карточек сохраняется. Вначале их ноль, то есть чётное число. Следовательно, после любого количества ходов оно останется чётным. Девять нечётно, поэтому требуемое состояние недостижимо. В доказательстве важны и разбор одного хода, и сравнение начала с целью.
Несколько попыток ещё не доказательство
Десять неудачных последовательностей показывают только то, что эти последовательности не сработали. Инвариант охватывает сразу все допустимые последовательности, независимо от длины. Чтобы рассуждение было полным, нельзя ограничиться случаем переворота двух белых карточек: позже могут появиться и другие пары. Также не стоит писать, что число чёрных всегда увеличивается. Оно может уменьшаться. Сохраняется именно чётность, а не направление изменения и не само количество.
Совпадение признака не всегда даёт решение
Если цель содержит чётное число чёрных карточек, найденный инвариант её не запрещает. Но в общем случае отсутствие запрета ещё не доказывает достижимость. Нужна конструкция или дополнительное рассуждение. Для наших свободных переворотов любую заданную чётную группу можно разбить на пары и перевернуть каждую пару один раз. Это уже доказательство возможности. При изменении правила, например разрешении трогать только определённые пары, такое построение может перестать работать. Поэтому каждый вывод следует связывать с точным условием задачи.
Попробуйте на практике
Решите похожую задачу для восьми белых карточек и сформулируйте два разных вида доказательства.
- Запишите правило: за ход переворачиваются любые две разные карточки; выбранная пара может повторяться.
- Докажите, что получить ровно семь чёрных карточек невозможно, перечислив изменения количества за один ход.
- Покажите, как получить чёрными карточки с номерами от первого до шестого, оставив остальные белыми.
- Сравните своё построение с тремя переворотами пар: первая и вторая, третья и четвёртая, пятая и шестая.
- Измените правило: разрешена только пара первая и вторая. Объясните, почему чётность теперь не отвечает на все вопросы о достижимости.
Как проверить результат. Невозможность семи обоснована сохраняющейся чётностью. Возможность шести подтверждена конкретными ходами. При ограниченной паре вы замечаете, что третья карточка вообще не меняет сторону.
Частые вопросы
Инвариант обязательно бывает числом?
Нет. Это может быть чётность, остаток, раскраска или другое свойство. Главное — доказать, что каждый допустимый ход его сохраняет.
Как понять, какой признак искать?
Начните с малых примеров и выпишите, что меняется за один ход. Если количество скачет на одинаковые кратные величины, стоит проверить остатки и чётность.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.