Докажите, что если последовательность удовлетворяет следующим условиям: Читать далее «M1437»
Рубрика: Задачи «Квант»
Математические задачи из детского физико-математического журнала «Квант»
M1459
Игроки A и B по очереди ходят конем на шахматной доске 1994х1994. Игрок А может делать только горизонтальные ходы, т.е. такие, при которых конь перемещается на соседнюю горизонталь. Игроку В разрешены только вертикальные ходы, при которых конь перемещается на соседнюю вертикаль. Игрок А ставит коня на поле, с которого начинается игра, и делает первый ход. При этом запрещено ставить коня на то поле, на котором он уже побывал в данной игре. Проигравшим считается игрок, которому некуда ходить. Докажите, что для игрока А существует выигрышная стратегия.
Первое решение.
Так как число всех возможных позиций в игре конечно, то один из двух игроков обязательно имеет выигрышную стратегию. Если у игрока А нет выигрышной стратегии, то игрок В правильно играя, выигрывает при любом первом ходе А. Докажем, что это невозможно. Для этого организуем две игры на двух досках. На первой доске А делает произвольный первый ход с поля х на поле у. На второй доске А ставит коня на поле у и ждет ответного хода В на первой доске, после чего в точности повторяет ход В на второй доске в качестве своего хода. На второй доске A делает вертикальные ходы, а В горизонтальные. Однако если повернуть доску на 90 °, то игра происходит в точности по правилам условия задачи. Далее игрок В делает горизонтальный ход на второй доске, который повторяется игроком А на первой доске в качестве своего хода и т.д. Заметим, что игрок В не может на второй доске попасть на поле х, так как В всегда ходит на поле одного цвета, отличного от цвета х. В этой двойной игре А всегда имеет возможность сделать очередной ход, если В имеет такую возможность. Поэтому проиграет В вопреки «предположению» что у него есть выигрышная стратегия.
Второе решение.
Выигрышная стратегия для игрока A такова. Он должен вначале игры поставить коня на любую клетку, из которой выходит стрелка (см. рисунок), и сделать ход в направлении, указанном стрелкой. После хода В конь вновь окажется в клетке, из которой выходит стрелка. А вновь движется по стрелке, и так далее. Видно, что у него всегда есть возможность сделать ход, поэтому победа ему гарантирована. При этом он никогда не попадает на клетки, в которых уже побывал.
