Условие:
В каждой клетке квадрата 101×101, кроме центральной, стоит один из двух знаков: «поворот» или «прямо». Машинка въезжает извне в произвольную клетку на границе квадрата, после чего ездит параллельно сторонам клеток, придерживаясь двух правил:
1) в клетке со знаком «прямо» она продолжает путь в том же направлении;
2) в клетке со знаком «поворот» она поворачивает на 90◦ (в любую сторону по своему выбору).
Центральную клетку квадрата занимает дом. Можно ли расставить знаки так, чтобы у машинки не было возможности врезаться в дом?
Решение:
Заметим, что если машинка может проехать из клетки A в клетку B, то она может проехать из клетки B в клетку A— проезжая тот же маршрут в обратном порядке. Поэтому достаточно доказать, что, выезжая из дома, машинка может выехать за границу квадрата. В самом деле, пусть машинка выезжает из центральной клетки на вверх. В каждой следующей клетке она сможет ехать на вверх или влево, никогда не двигаясь вниз и вправо. Тогда не позднее, чем через 101 шаг, она заведомо выйдет за границы квадрата.