Задача 35199

Темы:    [ Деревья ] [ Принцип крайнего (прочее) ]

Сложность: 3+ Классы: 7,8,9

Условие

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

Подсказка

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

Решение

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

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

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

web-сайт

задача