Если в Peg Solitaire на английской доске в 33 лунки начать с пустого центра, последний шарик можно оставить только в пяти лунках (статья о том, как оставить шарик в центре). В остальных 28 лунках оставить его нельзя, как умело ни играй.

Почему можно так уверенно утверждать? В этой статье объясняется причина: доску раскрашивают по диагонали в три цвета.

Раскрашиваем доску по диагонали в три цвета

Лунки красят в красный, синий и золотой так, чтобы получились диагональные полосы, идущие из правого верхнего угла в левый нижний. Цвета полос повторяются по порядку слева сверху вправо вниз: красный, синий, золотой, красный, синий, золотой…

abcdefg1234567

Цвет края лунки — это цвет раскраски. Если посмотреть на три лунки подряд по вертикали или горизонтали, в них всегда по одной красной, синей и золотой.

За один ход число шариков каждого из трёх цветов меняется на один

Один ход в Peg Solitaire использует три лунки подряд по вертикали или горизонтали (шарик, который идёт; шарик, через который прыгают; лунка назначения). Эти три лунки — ровно по одной каждого цвета.

После хода:

  • цвет шарика, который шёл: на один меньше
  • цвет шарика, через который перепрыгнули: на один меньше (он снят)
  • цвет лунки назначения: на один больше

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

Что не меняется

Чётность всех трёх цветов с каждым ходом меняется одновременно. Поэтому «сочетание чётности трёх цветов» может быть только

  • таким же, как в начале, или
  • таким, где все три значения начала перевёрнуты.

Если на английской доске в 33 лунки начать с пустого центра, шариков будет 10 красных, 11 синих и 11 золотых (центральная d4 — красная лунка). В записи через чётность:

МоментКрасныеСиниеЗолотые
В началечётноенечётноенечётное
Если перевернутьнечётноечётноечётное

Сколько бы ходов ни сделали, доска окажется в одном из этих двух сочетаний.

Последний шарик может остаться только в красной лунке

Когда остался один шарик, только число шариков его цвета равно 1 (нечётное), а у двух других цветов 0 (чётное).

  • Если он остался в красной лунке, это «нечётное, чётное, чётное», как во второй строке таблицы. Так бывает.
  • Если он остался в синей или золотой, это «чётное, нечётное, чётное» или «чётное, чётное, нечётное», и ни с одной строкой таблицы это не совпадает. Так не бывает.

То есть последний шарик может остаться только в красной лунке.

То же самое для диагоналей в другую сторону

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

abcdefg1234567

И здесь центральная d4 — красная лунка, и по той же причине последний шарик может остаться только в красной лунке.

Лунок, которые красные при обеих раскрасках, только пять.

abcdefg1234567

Центральная d4 и середины концов рукавов d1, a4, g4 и d7. Это пять лунок, в которых можно оставить последний шарик. То, что шарик можно оставить в каждой из пяти, я проверил программой, которая ищет ходы.

Почему французскую доску в 37 лунок нельзя пройти

Известно, что на французской доске в 37 лунок (английская плюс четыре лунки во внутренних углах), если начать с пустого центра, один шарик не оставить ни при какой игре. Это тоже видно по такой раскраске.

У 36 шариков при пустом центре красных 12, синих 12 и золотых 12. Все три цвета чётные. По ходу игры будет либо «чётное, чётное, чётное», либо «нечётное, нечётное, нечётное».

А у доски, где остался один шарик, при любой лунке «нечётный только один цвет, а два других чётные». Ни одно сочетание не подходит, поэтому французскую доску, начав с центра, нельзя довести до одного шарика.

Если начинать с другой пустой лунки, то же самое проверяется тем же расчётом. На французской доске в 37 лунок для 21 из 37 лунок уже двумя раскрасками в разные стороны видно, что, начав с неё пустой, один шарик не оставить.

Эта идея используется и в приложении

«Подсказка» в приложении «Peg Solitaire», когда ищет следующий ход, использует эту трёхцветную раскраску. Позиции, где при любой игре шарик не удастся оставить в нужной лунке, определяются как нерешаемые ещё до просмотра ходов вперёд, и дальше их проверять не нужно.

Итог

  • Если раскрасить доску по диагонали в три цвета, с каждым ходом чётность числа шариков всех трёх цветов меняется на противоположную.
  • Поэтому лунки, в которых можно оставить последний шарик, определяются начальной доской.
  • Если на английской доске в 33 лунки начать с центра, шарик можно оставить только в пяти лунках: d4, d1, a4, g4 и d7.
  • Если на французской доске в 37 лунок начать с центра, один шарик оставить нельзя.

Но лунки, про которые раскраска сказала «возможно», не всегда действительно удаётся занять. Раскраска — это инструмент для обнаружения «невозможного», а возможность нужно проверять, находя ходы.