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

Проект МЦНМО
при участии
школы 57
Задача 109679
Темы:    [ Шахматные доски и шахматные фигуры ]
[ Теория алгоритмов (прочее) ]
[ Итерации ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Назовём лабиринтом шахматную доску 8×8, на которой между некоторыми полями поставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа находится край доски или перегородка, остаётся на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Программист пишет программу – конечную последовательность указанных команд, и даёт её пользователю, после чего пользователь выбирает лабиринт и помещает в него ладью на любое поле. Верно ли, что программист может написать такую программу, что ладья обойдёт все доступные поля в лабиринте при любом выборе пользователя?


Решение

Занумеруем всевозможные начальные положения, то есть пары (лабиринт, положение ладьи) – их конечное число. Составим программу П1 обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение №2. Применим программу П1 и, если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу П2. Применим программу П2 к ладье в 3-м начальном положении, снова допишем программу и т.д.


Ответ

Верно.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1998
Этап
Вариант 5
Класс
Класс 9
задача
Номер 98.5.9.4

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

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