Математика · объяснение и практика

Как неизменный остаток запрещает достижение игрового состояния

Ищем остаток, сохраняемый разрешёнными ходами, доказываем невозможность цели без перебора маршрутов и проверяем, чего одного инварианта ещё недостаточно установить.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Если каждый разрешённый ход меняет число на кратное m, его остаток по модулю m сохраняется. Цель с другим остатком недостижима. Совпадение остатка снимает этот запрет, но само по себе ещё не строит допустимую последовательность ходов.

Неизменная характеристика вместо длинного перебора

В игре к текущему целому числу разрешено прибавлять шесть или девять. Стартуем с четырёх. Оба изменения кратны трём, поэтому после любого числа ходов остаток остаётся равным одному. Это свойство называется инвариантом. Оно не сообщает точное текущее число, но выделяет класс, из которого разрешённые операции не способны вывести состояние.

Для доказательства достаточно проверить начальное состояние и один произвольный ход. Если свойство верно до хода, прибавление кратного трём сохраняет его после. Повторение этого аргумента охватывает любую конечную длину игры. Не нужно по очереди вычислять все возможные маршруты, число которых быстро растёт даже при двух доступных действиях.

Как отличить запрет от построенного пути

Цель 26 даёт остаток два по модулю три, поэтому из четырёх она недостижима. Это окончательный отрицательный ответ. Для цели 19 остаток подходящий, и можно показать путь 4 → 10 → 19 прибавлением шести и девяти. Явный маршрут подтверждает достижимость, тогда как один инвариант только не запрещал её.

Цель 7 тоже имеет остаток один, но недостижима в этой игре. Положительная разность со стартом равна трём, а каждый непустой ход увеличивает число как минимум на шесть. Значит, условие остатка необходимо, но недостаточно. Здесь дополнительное препятствие связано с величиной и направлением изменений, а не с обнаруженным классом по модулю.

Пример

От числа 5 разрешено прибавлять 4 или 8. Какая из целей 13, 17 и 18 запрещена уже по остатку?

Начальный остаток по модулю четыре равен одному и сохраняется. Числа 13 и 17 имеют тот же остаток и достигаются, а 18 оставляет два. Поэтому цель 18 невозможна без всякого перебора ходов.

Как выбирать подходящий инвариант

Для числовых добавлений естественно проверить общий делитель всех изменений. Для перестановок или перекрашиваний полезной характеристикой может быть чётность, сумма по модулю или иной счётчик. Кандидат нужно проверить на каждом типе разрешённого хода. Если хотя бы один тип его нарушает, свойство не является инвариантом всей игры, даже если работает на большинстве примеров.

Условия о направлении ходов, запрете отрицательных состояний и числе шагов сохраняются отдельно. Если правила изменились и теперь разрешено вычитать девять, старый аргумент о минимальном положительном приросте уже неприменим, хотя остаток по модулю три остаётся неизменным. Разделение инварианта и дополнительных ограничений позволяет понять, какой вывод сохраняется после изменения задачи.

От чтения к действию

А теперь — вы

Старт 2, разрешено прибавлять 5 или 10. Какая цель невозможна уже из-за остатка по модулю пять?

Частые вопросы

Если остатки совпадают, путь всегда существует?

Нет. Могут мешать величина шага, направление изменений или другие ограничения. Нужно отдельное построение или достаточный критерий.

Сколько ходов нужно перебрать для доказательства инварианта?

Не требуется конечный предел перебора. Проверяют начальное состояние и сохранение свойства каждым разрешённым типом хода.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться