Игры без алгоритма

Игры без алгоритма

Победитель определялся автоматически, независимо от игры обоих соперников.

Задача.

Существует одна из разновидностей шахмат (рис. 9) – когда каждый из игроков делает по два хода. Доказать, что в такой игре у второго игрока не может существовать выигрышная стратегия.

Рис. 9. Шахматы

Доказательство.

Для доказательства воспользуемся так называемым «методом от противного». Пусть такая стратегия у второго игрока существует.

Тогда первый игрок может своим ходом сделать следующий «маневр»: походит любым конем первым своим ходом, а вторым ходом вернет коня обратно.

Что произойдет в этом случае: получается, что второй игрок как бы станет первым, так как перед его ходом на доске снова начальная позиция. Тогда, если бы существовала выигрышная стратегия для второго игрока, то после такой «передачи хода», она стала бы выигрышной для первого игрока – и партию выиграл бы он. Значит, она не была бы выигрышной для второго игрока – получили противоречие.

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

Доказано.

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

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

⇐ Предыдущая 1 23