|
|
 |
Условие
Игроки A и B по очереди ходят конем на шахматной доске 1994×1994. Игрок A может делать только горизонтальные ходы, то есть такие, при которых конь перемещается на соседнюю горизонталь. Игроку B разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок A ставит коня на поле, с которого начинается игра, и делает первый ход. При этом каждому игроку запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока A существует выигрышная стратегия.
Решение
Так как игра заканчивается не более, чем через 1994² ходов, то один из двух игроков обязательно имеет выигрышную стратегию. Если у игрока A нет выигрышной стратегии, то игрок B, правильно играя, выигрывает при любом первом ходе игрока A. Докажем, что это невозможно. Для этого организуем две игры на двух досках (на второй доске A будет делать только вертикальные ходы, а B – только горизонтальные; заметим, что если повернуть доску на 90°, то игра происходит в точности по правилам условия задачи). На первой доске A делает произвольный первый ход с поля x на поле y. На второй доске A ставит коня на поле y и ждёт ответного хода B на первой доске. После чего в точности повторяет ход B на второй доске в качестве своего хода. Далее игрок B делает горизонтальный ход на второй доске, который повторяется игроком A на первой доске в качестве своего хода, и т.д. Заметим, что игрок B не может на второй доске попасть на поле x, так как B всегда ходит на поле цвета, отличного от цвета x. В этой двойной игре A всегда имеет возможность сделать очередной ход, если B имеет такую возможность. Поэтому на одной из двух досок проиграет B вопреки предположению, что у него есть выигрышная стратегия.
