|
|
 |
Условие
Людоедом называется фантастическая шахматная фигура, которая может ходить как шахматный король – на соседнюю клетку по вертикали или горизонтали, но не может ходить по диагонали. Два людоеда стоят на противоположных угловых полях шахматной доски и начинают ходить по очереди. Людоеду, вставшему на клетку, где уже стоит другой людоед, разрешается им пообедать. Кто кого съест при правильной игре и как ему надо для этого играть?
Решение
Разобьём клетки доски на диагонали, параллельные той, где изначально расположены людоеды. Всего таких диагоналей 15. Заметим, что каждым ходом людоед перемещается на соседнюю диагональ.
Укажем стратегию, позволяющую второму людоеду пообедать. Пусть для определенности он начинает игру из правого верхнего угла. Тогда он должен всегда ходить влево или вниз, и при этом вставать на ту же диагональ, на которую перед этим встал первый людоед. При этом после любого парного хода людоеды окажутся в противоположных углах некоторого квадрата. Размеры этого квадрата будут либо уменьшаться (если первый людоед будет ходить вправо или вверх), либо не будут изменяться. Но первый людоед не сможет постоянно ходить влево или вниз – сделав несколько таких ходов, он обязательно попадёт в положение, когда ему придется ходить вверх или вправо. Таким образом, размеры квадрата в ходе игры будут уменьшаться. Когда они уменьшатся до 2×2, первый людоед будет вынужден, чтобы его не съели, ходить влево или вниз, но эти ходы вскоре закончатся, и он проиграет.
Ответ
Второй людоед съест первого.
Замечания
Посмотрим на расстояние между двумя людоедами – количество ходов, которые необходимо сделать, чтобы дойти от одного людоеда до другого. Изначально это расстояние равно 13. После каждого хода любого людоеда это расстояние либо увеличивается на 1, либо уменьшается на 1, то есть меняет чётность. Заметим, что людоед может пообедать данным ходом, если к этому моменту расстояние между людоедами стало равно 0. Так как перед любым ходом первого людоеда расстояние между людоедами нечётно, то первый людоед никогда не сможет пообедать вторым, даже если бы второй пытался поддаться.
