Задача 105160

Темы:    [ Обход графов ] [ Ориентированные графы ] [ Индукция (прочее) ]

Сложность: 4+ Классы: 9,10,11

Условие

Авторы: Межиров И.В., Спивак А.В., Чернов А. А.

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

Решение

  Пусть внутри страны, пока ещё не поделённой на губернии, возникла автономная область, состоящая из одного города. Эту область, во-первых, можно разделить на три губернии (две пустые), и во-вторых, она удовлетворяет условию как самостоятельная страна, то есть при удалении всех остальных городов. Будем добавлять города к автономной области с сохранением этих двух условий.
  Предположим, что область содержит не все города. Тогда найдётся дорога, ведущая из города области (обозначим его через X) в город, ещё не принадлежащий автономной области (назовём его Y). Рассмотрим несамопересекающийся путь (последовательность дорог), ведущий из Y в X (см. рис.).

  Предположим, что на этом пути есть город Z, лежащий в автономной области. Тогда из X можно добраться до Z двумя несамопересекающимися путями: один путь идёт через Y, а второй идёт только по городам области (такой путь существует, потому что для области выполнено условие задачи, как и для всей страны). Но это противоречит условию. Следовательно, путь из Y в X не содержит других городов из области, кроме X.
  Теперь присоединим все города на этом пути (включая Y) к автономной области и отнесём их поочерёдно в те две губернии, в которые X не входит. Все дороги, соединяющие два присоединённых города, - это дороги на пути  Y → X,  иначе между ними было бы два пути. Аналогично все дороги, соединяющие присоединённый город с городом, уже имевшимся в области – это дорога из X в Y и последняя дорога на пути  Y → X.  Следовательно, область будет правильно разделена на губернии.
  Два несамопересекающихся пути от одного города к другому по области невозможны, иначе бы вся страна не удовлетворяла условию. От каждого города области можно доехать (по области) до X, а от X – до всех остальных, поэтому по крайней мере один путь от одного города области до другого всегда существует. Значит, новая область тоже удовлетворяет условию.
  На каждом описанном шаге область увеличивается хотя бы на один город (Y). Следовательно, рано или поздно все города будут присоединены. В этот момент область совпадёт со всей страной и при этом будет разделена на губернии.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	66
Год	2003
вариант
Класс	10
задача
Номер	5