Игра в шоколадку (игра «Щёлк» Дэвида Гейла), или Чёрные начинают и выигрывают
Есть плитка шоколада, традиционно поделенная на дольки m*n.
Играют два игрока.
Суть игры состоит в том, чтобы не съесть «отравленную» дольку, находящуюся в левом нижнему углу.
Правила следующие: игрок выбирает дольку, а затем отламывает и съедает её, а также все дольки правее и выше.
Доказать, что при условии обладания выигрышной стратегией всегда выигрывает 1-й игрок (кроме шоколадки с единственной долькой, потому что в этом случае он-то её и съедает первым же ходом).
Пусть у 2-го игрока есть выигрышная стратегия (её алгоритм на данный момент неизвестен, но сейчас речь не об этом). Докажем, что в этом случае выигрышная стратегия есть и у 1-ого игрока.
Цитата из Википедии: «Предположим, что первым ходом первый игрок съел только правую верхнюю дольку, и рассмотрим ход второго игрока, ведущий к выигрышной стратегии; тогда первый игрок может сам походить так своим первым ходом, тем самым «позаимствовав» стратегию второго игрока. Значит, у второго игрока не может быть выигрышной стратегии, а потому она есть у первого» (ц).
Дополним сказанное.
Предположим, партия началась раньше, и минусовые ходы (все ходы до откусывания первой реальной дольки) происходили за пределами реального поля. Пусть ход с откусыванием верхней правой дольки шоколада – это ход 0. Тогда первый выигрышный ход на реальном поле – это ход 1.
Если 2-й делает ход 0, то 1-й делает ход 1 и выигрывает,
и Если 2-й не делает ход 0 (а по-прежнему сидит в виртуале и минусе), то 1-й делает ход 1 и выигрывает,
Мораль: 1-й выигрывает всегда.
Иными словами, согласно принципу пресуппозиции (А следование В)*(не-А следование В) = В:
(А) Если 2-й делает ход 0, то (В) 1-й делает ход 1 и выигрывает,
и (не-А) Если 2-й не делает ход 0, то (В) 1-й делает ход 1 и выигрывает,
Значит, (В) 1-й выигрывает всегда.
Это доказательство неконструктивно, то есть доказывает только сам факт существования решения проблемы, но не предлагает определённой методики.
Тем не менее, для квадратной шоколадки z*z такая методика (выигрышная стратегия) есть. Последняя долька [z] при этом является последним реально возможным (и проигрышным) ходом из всего (бес)конечного виртуально-реального поля. (П.С. Если идти именно с «той» стороны, потому что с «другой» стороны всегда есть снова тот же самый ход 0... – Л.Б.)
1-й ход 1-ого игрока (при условии, что игрок стремится к выигрышу) – это ход 0 следование 1. Этот ход обязан сразу быть «предельным» по той причине, что если он не будет таким, то 2-й игрок сам докусает шоколадку до предельного состояния 1. То есть ход 1 – это ход в крайнюю перед последней долькой позицию. Позиции [у] для 1 хода не годятся ни та, ни другая, поскольку в этом случае 2-й откусит всё, кроме [z], включая второй [у], и 1-ому останется только [z].
Теперь 1-ому достаточно делать вслед за 2-м симметричные ходы по другой грани, и тогда последним ходом, не имеющим «зеркального отражения» будет для 2-ого ход [z] – проигрышный. А у 1-ого игрока хода больше не останется (кроме нового перехода в следующее виртуальное поле), что и означает его выигрыш в реальной игре, а также тот факт, что 2-й съел граничную между реальностью и новым виртуалом «отравленную дольку».