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

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

Условие

Дед барона К.Ф.И. фон Мюнхгаузена построил квадратный замок, разделил его на 9 квадратных залов и в центральном разместил арсенал. Отец барона разделил каждый из восьми оставшихся залов на 9 равных квадратных холлов и во всех центральных холлах устроил зимние сады. Сам барон разделил каждый из 64 свободных холлов на 9 равных квадратных комнат и в каждой из центральных комнат устроил бассейн, а остальные сделал жилыми. Барон хвастается, что ему удалось обойти все жилые комнаты, побывав в каждой по одному разу, и вернуться в исходную (в каждой стене между двумя соседними жилыми комнатами проделана дверь). Могут ли слова барона быть правдой?


Решение

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


Ответ

Могут.

Замечания

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

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

олимпиада
Название Московская математическая олимпиада
год
Номер 56
Год 1993
вариант
Класс 10
задача
Номер 2

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

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