Разделы 
Дополнительно
Задача по математике - 1883
2019-01-21 
Назовем лабиринтом шахматную доску $8 \times 8$, на которой между некоторыми полями поставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа находится край доски или перегородка, остается на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Программист пишет программу - конечную последовательность указанных команд, и дает ее пользователю, после чего пользователь выбирает лабиринт и помещает в него ладью на любое поле. Верно ли, что программист может написать такую программу, что ладья обойдет все доступные поля в лабиринте при любом выборе пользователя?
Решение:
Занумеруем всевозможные начальные положения, т. е. пары (лабиринт, положение ладьи) - их конечное число. Составим программу $П_1$ обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение 2. Применим программу $П_1$, и если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу $П_2$. Применим программу $П_2$ к ладье в 3-м начальном положении, снова допишем программу и т. д.
Ответ. Верно.
Назовем лабиринтом шахматную доску $8 \times 8$, на которой между некоторыми полями поставлены перегородки. По команде ВПРАВО ладья смещается на одно поле вправо или, если справа находится край доски или перегородка, остается на месте; аналогично выполняются команды ВЛЕВО, ВВЕРХ и ВНИЗ. Программист пишет программу - конечную последовательность указанных команд, и дает ее пользователю, после чего пользователь выбирает лабиринт и помещает в него ладью на любое поле. Верно ли, что программист может написать такую программу, что ладья обойдет все доступные поля в лабиринте при любом выборе пользователя?
Решение:
Занумеруем всевозможные начальные положения, т. е. пары (лабиринт, положение ладьи) - их конечное число. Составим программу $П_1$ обхода всех полей для первого начального положения. Предположим теперь, что начальным было положение 2. Применим программу $П_1$, и если ладья обошла не все поля, допишем в конце несколько команд, чтобы обойти оставшиеся поля. Получим программу $П_2$. Применим программу $П_2$ к ладье в 3-м начальном положении, снова допишем программу и т. д.
Ответ. Верно.
