4 Доказательство в картинках

Две проверки по остаткам доказывают правило для всех n. Окно меток находит период.

Можно взять:

Две проверки по остаткам

  • (А) из П нельзя попасть в Пне проверено
  • (Б) из В можно попасть в Пне проверено
ход в В ход в П
Подробнее: таблица ходов и лемма

В клетке — остаток после хода, ★ — это П-остаток.

Лемма. Пусть X — позиции с П-остатками. Если (А) из X нельзя одним ходом попасть в X, а (Б) из любой позиции вне X можно, то X — ровно П-позиции.

Почему: индукция по n. Метка n зависит только от меньших позиций, а (А) и (Б) — это и есть правило «В, если есть ход в П».

Окно повторилось — период найден

k — наибольший ход. Метка зависит только от k предыдущих меток, поэтому повтор окна = повтор навсегда.

    Подробнее

    Разных окон из k меток не больше 2k, поэтому повтор обязательно наступит.

    Если окно с позиции i совпало с окном с позиции j, то метки n и n + (j − i) совпадают для всех n ≥ i: каждую следующую метку считаем по одинаковому окну.

    Запрет двойки: почему n = 5 стал В

    Ходы из кучи в 5 камней до и после запрета.

    Позиции 0–35: обведены те, что поменяли метку.