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

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

Условие

Автор: Антонов М.

Лабиринт представляет собой квадрат 8×8, в каждой клетке 1×1 которого нарисована одна из четырёх стрелок (вверх, вниз, вправо, влево). Верхняя сторона правой верхней клетки – выход из лабиринта. В левой нижней клетке находится фишка, которая каждым своим ходом перемещается на одну клетку в направлении, указанном стрелкой. После каждого хода стрелка в клетке, в которой только что была фишка, поворачивается на 90° по часовой стрелке. Если фишка должна сделать ход, выводящий ее за пределы квадрата 8×8, она остается на месте, а стрелка также поворачивается на 90° по часовой стрелке. Докажите, что рано или поздно фишка выйдет из лабиринта.


Решение

  Предположим, что фишка никогда не выйдет из лабиринта. Тогда на клетку с номером 1 (см. рис.) фишка попадет конечное число раз (менее четырёх), так как в противном случае, когда стрелка покажет на выход, фишка из лабиринта уйдет.

  Аналогично получаем, что после того, как фишка в последний раз побывает на поле 1, она конечное число раз побывает на полях с номером 2.
  Продолжая рассуждения, получаем, что после того, как фишка в последний раз побывала на полях с номерами k,  1 ≤ k ≤ 14,  она конечное число раз побывает на каждом поле с номером   k + 1 . Значит, на каждом поле фишка побывает конечное число раз, что противоречит неограниченности числа ходов. Следовательно, фишка должна выйти из лабиринта.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1999
Этап
Вариант 4
Класс
Класс 10
задача
Номер 99.4.10.4
олимпиада
Название Всероссийская олимпиада по математике
год
Год 1999
Этап
Вариант 4
Класс
Класс 9
задача
Номер 99.4.9.4

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

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