ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111908
Темы:    [ Геометрия на клетчатой бумаге ]
[ Теория алгоритмов (прочее) ]
[ Индукция в геометрии ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В каждой клетке квадрата 101×101, кроме центральной, стоит один из двух знаков: "поворот" или "прямо". Машинка въезжает извне в произвольную клетку на границе квадрата, после чего ездит параллельно сторонам клеток, придерживаясь двух правил:
  1) в клетке со знаком "прямо" она продолжает путь в том же направлении;
  2) в клетке со знаком "поворот" она поворачивает на 90° (в любую сторону по своему выбору).
Центральную клетку квадрата занимает дом. Можно ли расставить знаки так, чтобы у машинки не было возможности врезаться в дом?


Решение 1

  Заметим, что если машинка может проехать из клетки A в клетку B, то она может проехать из клетки B в клетку A – проезжая тот же маршрут в обратном порядке. Поэтому достаточно доказать, что, выезжая из дома, машинка может выехать за границу квадрата.
  Пусть знаки как-то расставлены. "Выпустим" машинку из дома. Пусть она движется согласно "правилам дорожного движения", поворачивая попеременно то вправо, то влево. Тогда она не может "зациклиться" и когда-то выйдет за пределы квадрата 101×101.


Решение 2

  Если машинка въезжает в правый нижний угол, то какой бы знак там ни стоял, она может проехать как вверх, так и налево (в зависимости от того, въезжает она в эту клетку снизу или справа). Поэтому правый нижний угол можно выкинуть и считать, что машинка сразу въезжает в оставшуюся часть.
  Самую правую клетку в нижнем ряду оставшейся части можно выкинуть аналогичным образом. Повторяя это рассуждение, каждый раз можно выкидывать из доски клетку, правее и ниже которой ничего нет, пока центральная клетка не станет доступна извне.


Ответ

Нельзя.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 72
Год 2009
Класс
Класс 8
задача
Номер 4
олимпиада
Название Московская математическая олимпиада
год
Номер 72
Год 2009
класс
Класс 9
задача
Номер 3
олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант весенний тур, сложный вариант, 8-9 класс
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .