Олимпиадная задача по комбинаторной геометрии: машинка и квадрат 101×101 (8-10 класс)
Задача
В каждой клетке квадрата 101×101, кроме центральной, стоит один из двух знаков: "поворот" или "прямо". Машинка въезжает извне в произвольную клетку на границе квадрата, после чего ездит параллельно сторонам клеток, придерживаясь двух правил:
1) в клетке со знаком "прямо" она продолжает путь в том же направлении;
2) в клетке со знаком "поворот" она поворачивает на 90° (в любую сторону по своему выбору).
Центральную клетку квадрата занимает дом. Можно ли расставить знаки так, чтобы у машинки не было возможности врезаться в дом?
Решение
Решение 1: Заметим, что если машинка может проехать из клетки A в клетку B, то она может проехать из клетки B в клетку A – проезжая тот же маршрут в обратном порядке. Поэтому достаточно доказать, что, выезжая из дома, машинка может выехать за границу квадрата.
Пусть знаки как-то расставлены. "Выпустим" машинку из дома. Пусть она движется согласно "правилам дорожного движения", поворачивая попеременно то вправо, то влево. Тогда она не может "зациклиться" и когда-то выйдет за пределы квадрата 101×101.
Решение 2: Если машинка въезжает в правый нижний угол, то какой бы знак там ни стоял, она может проехать как вверх, так и налево (в зависимости от того, въезжает она в эту клетку снизу или справа). Поэтому правый нижний угол можно выкинуть и считать, что машинка сразу въезжает в оставшуюся часть.
Самую правую клетку в нижнем ряду оставшейся части можно выкинуть аналогичным образом. Повторяя это рассуждение, каждый раз можно выкидывать из доски клетку, правее и ниже которой ничего нет, пока центральная клетка не станет доступна извне.
Ответ
Нельзя.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь