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