Выиграть, не зная как

В главе 2 мы говорили об играх, в которых участники делают свои ходы поочередно и которые заканчиваются через определенное число ходов. Теоретически можно проанализировать все возможные последовательности ходов и найти оптимальную стратегию. Это сравнительно легко, когда играешь в крестики-нолики, и невозможно (во всяком случае пока) в шахматах. В игре, о которой пойдет речь, оптимальная стратегия неизвестна. Тем не менее, даже не зная, к чему сводится оптимальная стратегия, можно утверждать: эта стратегия обеспечит победу игроку, сделавшему первый ход.

ZECK – игра в точки с участием двух игроков. Цель каждого игрока – заставить соперника удалить последнюю точку. Игра начинается с расположения точек в форме прямоугольника любого размера, скажем 7 × 4:

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

Во время каждого раунда должна быть удалена минимум одна точка. Проигрывает тот, кто удаляет последнюю точку.

В случае прямоугольника любого размера, в котором есть хотя бы две точки, у первого игрока должна быть выигрышная стратегия. Однако в текущий момент она неизвестна. Можно проанализировать все возможные ходы и найти такую стратегию для любой конкретной игры, скажем для игры с прямоугольником 7 × 4. Тем не менее оптимальная стратегия для всех возможных размеров прямоугольника с точками остается неизвестной. Как можно доказать, у кого из игроков есть выигрышная стратегия, даже зная, в чем именно она состоит?