|
|
 |
Условие
В некотором государстве 101 город.
а) Каждый город соединен с каждым из остальных дорогой с односторонним движением, причём в каждый город входит 50 дорог и из каждого города выходит 50 дорог. Докажите, что из каждого города можно доехать в любой другой, проехав не более чем по двум дорогам.
б) Некоторые города соединены дорогами с односторонним движением, причём в каждый город входит 40 дорог и из каждого города выходит 40 дорог. Докажите, что из каждого города можно добраться до любого другого, проехав не более чем по трём дорогам.
Решение
Рассмотрим города А и В. Пусть соединяющая их дорога ведёт из B в A.
а) Рассмотрим 50 городов, в которые входят дороги из А, и 50 городов, из которых выходят дороги в В. Так как 50 + 50 > 99, есть город C, принадлежащий обоим множеством. Значит, можно проехать по маршруту ACB.
б) Пусть первая группа – 40 городов, в которые ведут дороги из A; вторая группа – 40 городов, из которых есть дорога в В, и сам город В; третья группа – оставшиеся 19 городов. Из городов первой группы выходит в совокупности 40·40 = 1600 дорог. Из них 40·39 : 2 = 780 дорог ведут в города первой группы и не более 40·19 = 760 дорог ведут в города третьей группы. Поскольку 780 + 760 < 1600, есть дорога, ведущая из первой группы во вторую, что и требовалось.
Источники и прецеденты использования
| книга | |
| Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
| Год издания | 1994 |
| Название | Ленинградские математические кружки |
| Издательство | Киров: "АСА" |
| Издание | 1 |
| глава | |
| Номер | 13 |
| Название | Графы-2 |
| Тема | Теория графов |
| задача | |
| Номер | 052 |
