2014-06-08
На шахматной доске размером $8 \times 8$ стоят 8 белых фишек на первой горизонтали и 8 черных - на восьмой. Игроки по очереди (начинают белые) делают ходы, состоящие в перемещении одной из своих фишек по вертикали на одну или несколько клеток вперед или назад. Запрещается снимать фишки с доски, ставить фишку на клетку, занятую фишкой противника, или перепрыгивать через нее. Проигрывает тот, кто не может сделать очередного хода. Доказать, что черные могут ходить так, чтобы наверняка выиграть.
Решение:
Разобьем доску на четыре части по две вертикали в каждой. Пусть черные в ответ на ход белых в какой-либо части делают ход в той же части. Тогда, если черные лишат белых возможности ходить в каждой из частей, то белые не смогут ходить вообще. Итак, достаточно описать выигрышную стратегию черных для случая, когда игра происходит в пределах двух вертикалей. Если белые передвигают свою фишку на k клеток вперед, то черные передвигают свою фишку, стоящую в другой вертикали, на k клеток вперед. Если же белые передвигают свою фишку на k клеток назад, то черные передвигают свою фишку, стоящую в той же вертикали, на k клеток вперед. Тогда после каждого хода черных расстояния между фишками, стоящими в одной вертикали, и фишками, стоящими в другой вертикали, становятся одинаковыми. Поэтому на любой ход белых черные имеют ответный ход, а значит, черные не могут проиграть. С другой стороны, черные ходят только вперед, так что игра обязательно закончится через конечное число ходов. Таким образом, черные выигрывают.