Задача 109679

Темы:    [ Шахматные доски и шахматные фигуры ] [ Теория алгоритмов (прочее) ] [ Итерации ]

Сложность: 5 Классы: 9,10,11

Условие

Авторы: Уфнаровский В.А., Шаповалов А.В.

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

Решение

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

Ответ

Верно.

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

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