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

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

Условие

В стране Мара расположено несколько замков. Из каждого замка ведут три дороги. Из какого-то замка выехал рыцарь. Странствуя по дорогам, он из каждого замка, стоящего на его пути, поворачивает либо направо, либо налево по отношению к дороге, по которой приехал. Рыцарь никогда не сворачивает в ту сторону, в которую он свернул перед этим. Доказать, что когда-нибудь он вернётся в исходный замок.


Решение

Все замки страны Мара связаны каким-то конечным числом дорог. Если рыцарь странствует по стране достаточно долго, то он проедет достаточно много дорог, поэтому хотя бы по одной дороге AB (A и B – замки) он проедет не менее пяти раз. При этом не менее трёх раз он проедет по этой дороге в одном и том же направлении (скажем, от A к B); поэтому, если из замка B, кроме BA, ведут еще две дороги BC и BD то рыцарь минимум дважды, – скажем, после i-го и после j-го посещения замка B, где  j > i,  – сворачивал, выезжая из B (куда он оба раза приезжал из A) в одну и ту же сторону, скажем, в сторону замка C. Но из условия тогда следует, что не только в i-е и в j-е посещение B рыцарь приехал в B из одного замка – из A, – но и в A он оба раза приезжал из одного и того же замка P (ведь если рыцарь после B свернул на дорогу BC, например, налево, то в A он должен был свернуть направо после посещения P). Аналогично этому устанавливается, что полностью совпадают пути рыцаря, предшествующие двум рассматриваемым посещениям замка B: в замок P он оба раза попал из одного и того же замка, и т. д. Но тогда, если рыцарь до i-го посещения B миновал, начиная с выезда из своего замка X, какое-то число k замков, то и за k замков до j-го посещения B он снова был в X, что и доказывает утверждение задачи.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 35
Год 1972
вариант
Класс 7
Тур 2
задача
Номер 4

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

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