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

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

Условие

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


Подсказка

Можно рассмотреть самую длинную цепь из дорог, концы этой цепи будут искомыми городами.


Решение

  Первый способ. Рассмотрим самую длинную цепь из дорог, то есть возьмём самую длинную последовательность попарно различных городов A1, A2, ..., Ak, в которой каждые два соседних города в этой последовательности соединены дорогой. Докажем, что из городов A1 и Ak выходит ровно одна дорога (соответственно в A2 и Ak–1). Пусть, например, из A1 идет дорога в некоторый город B, отличный от A2. Если B – один из городов A3, ..., Ak, то возникает цикл из дорог, что противоречит условию. Таким образом, город B отличен от городов A1, A2, ..., Ak. Следовательно, в последовательности городов B, A1, A2, ..., Ak города попарно различны и соседние города соединены дорогой. Но эта последовательность содержит больше k городов вопреки выбору последовательности A1, A2, ..., Ak.

  Второй способ. См. задачу 31098 в).

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

web-сайт
задача

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

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