Олимпиадная задача: выход фишки из лабиринта 8×8 со стрелками — доказательство
Задача
Лабиринт представляет собой квадрат 8×8, в каждой клетке 1×1 которого нарисована одна из четырёх стрелок (вверх, вниз, вправо, влево). Верхняя сторона правой верхней клетки – выход из лабиринта. В левой нижней клетке находится фишка, которая каждым своим ходом перемещается на одну клетку в направлении, указанном стрелкой. После каждого хода стрелка в клетке, в которой только что была фишка, поворачивается на 90° по часовой стрелке. Если фишка должна сделать ход, выводящий ее за пределы квадрата 8×8, она остается на месте, а стрелка также поворачивается на 90° по часовой стрелке. Докажите, что рано или поздно фишка выйдет из лабиринта.
Решение
Предположим, что фишка никогда не выйдет из лабиринта. Тогда на клетку с номером 1 (см. рис.) фишка попадет конечное число раз (менее четырёх), так как в противном случае, когда стрелка покажет на выход, фишка из лабиринта уйдет.
Продолжая рассуждения, получаем, что после того, как фишка в последний раз побывала на полях с номерами k, 1 ≤ k ≤ 14, она конечное число раз побывает на каждом поле с номером k + 1 . Значит, на каждом поле фишка побывает конечное число раз, что противоречит неограниченности числа ходов. Следовательно, фишка должна выйти из лабиринта.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь