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

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

Условие

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


Решение

  Докажем, что
    а) от каждой зелёной площади можно доехать до синей;
    б) от синей площади можно доехать до любой зелёной.
  Условимся обозначать направление движения на улицах стрелками.

  а) Предположим, что от зелёной площади A1 нельзя доехать до синей площади. Поскольку уехать с площади A1 можно, то от неё, проехав по одной улице, мы доедем до зелёной площади A2. От площади A2 тоже нельзя доехать до синей площади. Выехав с неё, мы доедем до площади A3, потом до A4 и т.д. Проехав по n улицам, мы вернёмся на площадь A1 и убедимся, что стрелки в городе расставлены так, как на рисунке. Но тогда на синюю площадь нельзя приехать, что противоречит условию.

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

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

журнал
Название "Квант"
год
Год 1974
выпуск
Номер 5
Задача
Номер М264

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

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