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

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

Условие

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


Решение

  Индукция по числу городских перекрёстков (из которых исходят более двух дорог).
  База. Если в Никитовке имеются всего два перекрёстка A и B, то утверждение очевидно: по условию из A в B ведут не менее двух дорог; поэтому достаточно установить по одной из этих дорог движение от A к B, а по второй – от B к A, мы сможем проехать от каждого перекрёстка до любого, отличного от него.
  Шаг индукции. Рассмотрим город Никитовку, имеющий  n + 1  перекрёсток и два соседних из этих перекрёстков – перекрёстки A и B, соединённые улицей AB. Поскольку после введения на улице AB (при её ремонте) одностороннего движения – скажем, от A к B – проехать от B к A было возможно, то из B в A ведёт некоторая не включающая улицы AB "цепочка" улиц (эту "цепочку" можно считать не имеющей самопересечений). Таким образом, мы приходим к существованию в Никитовке "кольца" s – замкнутой сети улиц, ведущей из A в B, а затем (через ряд "промежуточных" перекрёстков) – снова в A.
  Рассмотрим теперь новый город, план которого получается из плана Никитовки "склеиванием" всех перекрёстков нашего кольца s в один перекрёсток S, из которого исходят все улицы, реально "упирающиеся" в кольцо s. Число перекрёстков такого условного города меньше  n + 1;  поэтому по предположению индукции в нём можно ввести по всем улицам одностороннее движение с соблюдением требований задачи. Если мы затем оставим движение по всем не входящим в кольцо s улицам таким же, каким оно было в этом новом городе, а по кольцу s пустим движение в одном (безразлично каком!) направлении, то на всех улицах Никитовки будет установлено одностороннее движение – и притом с каждого перекрёстка можно будет проехать в любой другой.

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

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

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

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