Разделы 
Дополнительно
Задача по математике - 1814
2019-01-20 
Игроки $A$ и $B$ по очереди ходят конем на шахматной доске $1994 \times 1994$. Игрок $A$ может делать только горизонтальные ходы, т. е. такие, при которых конь перемещается на соседнюю горизонталь. Игроку $B$ разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок $A$ ставит коня на поле, с которого начинается игра, и делает первый ход. При этом каждому игроку запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока $A$ существует выигрышная стратегия.
Решение:
Так как игра заканчивается не более, чем через 19942 ходов, то один из двух игроков обязательно имеет выигрышную стратегию. Если у игрока $А$ нет выигрышной стратегии, то игрок $B$, правильно играя, выигрывает при любом первом ходе игрока $A$. Докажем, что это невозможно. Для этого организуем две игры на двух досках (на второй доске $A$ будет делать только вертикальные ходы, а $B$ - только горизонтальные; заметим, что если повернуть доску на $90^{\circ}$, то игра происходит в точности по правилам условия задачи). На первой доске $А$ делает произвольный первый ход с поля $x$ на поле $у$. На второй доске $А$ ставит коня на поле $у$ и ждет ответного хода $B$ на первой доске. После чего в точности повторяет ход $B$ на второй доске в качестве своего хода. Далее игрок $B$ делает горизонтальный ход на второй доске, который повторяется игроком $A$ на первой доске в качестве своего хода, и т. д. Заметим, что игрок $B$ не может на второй доске попасть на поле $х$, так как $B$ всегда ходит на поле одного цвета, отличного от цвета $х$. В этой двойной игре $A$ всегда имеет возможность сделать очередной ход, если $B$ имеет такую возможность. Поэтому на одной из двух досок проиграет $B$ вопреки предположению, что у него есть выигрышная стратегия.
Игроки $A$ и $B$ по очереди ходят конем на шахматной доске $1994 \times 1994$. Игрок $A$ может делать только горизонтальные ходы, т. е. такие, при которых конь перемещается на соседнюю горизонталь. Игроку $B$ разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок $A$ ставит коня на поле, с которого начинается игра, и делает первый ход. При этом каждому игроку запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока $A$ существует выигрышная стратегия.
Решение:
Так как игра заканчивается не более, чем через 19942 ходов, то один из двух игроков обязательно имеет выигрышную стратегию. Если у игрока $А$ нет выигрышной стратегии, то игрок $B$, правильно играя, выигрывает при любом первом ходе игрока $A$. Докажем, что это невозможно. Для этого организуем две игры на двух досках (на второй доске $A$ будет делать только вертикальные ходы, а $B$ - только горизонтальные; заметим, что если повернуть доску на $90^{\circ}$, то игра происходит в точности по правилам условия задачи). На первой доске $А$ делает произвольный первый ход с поля $x$ на поле $у$. На второй доске $А$ ставит коня на поле $у$ и ждет ответного хода $B$ на первой доске. После чего в точности повторяет ход $B$ на второй доске в качестве своего хода. Далее игрок $B$ делает горизонтальный ход на второй доске, который повторяется игроком $A$ на первой доске в качестве своего хода, и т. д. Заметим, что игрок $B$ не может на второй доске попасть на поле $х$, так как $B$ всегда ходит на поле одного цвета, отличного от цвета $х$. В этой двойной игре $A$ всегда имеет возможность сделать очередной ход, если $B$ имеет такую возможность. Поэтому на одной из двух досок проиграет $B$ вопреки предположению, что у него есть выигрышная стратегия.
