Условие
Между двумя странами установлено авиационное сообщение так, что любые два города из разных стран соединены ровно одним авиарейсом и только в одну сторону, причём из каждого города можно куда-нибудь вылететь. Докажите, что найдутся четыре города $A$, $B$, $C$, $D$, которые можно посетить, перелетая непосредственно из $A$ в $B$, из $B$ в $C$, из $C$ в $D$, из $D$ в $A$.
Подсказка
Докажите и используйте следующий факт: если обозначить через $M(A)$ множество всех городов второй страны, в которые можно вылететь из города $A$ первой страны, то найдутся два таких множества $M(A)$ и $M(C)$, что в одном из них есть город, не лежащий в другом, и наоборот.
Решение
Для каждого города $A$ первой страны обозначим через $M(A)$ множество всех городов второй страны, в которые есть рейс из $A$ (тогда из остальных городов второй страны, не входящих в $M(A)$, можно, наоборот, вылететь в $A$). По условию, из каждого города первой страны можно вылететь в какой-то из городов второй страны, поэтому каждое такое множество $M(A)$ непусто, т. е. содержит хотя бы один город. Если предположить, что для любых двух таких множеств одно содержится в другом, то тогда множество, в котором наименьшее число городов, содержится в любом из остальных. Потому в какой-нибудь город, принадлежащий этому множеству, есть рейс из каждого города первой страны, но ни в один из них нет обратного рейса, что противоречит условию задачи. Значит, это предположение неверно, и найдутся два таких множества $M(A)$ и $M(C)$, что в первом есть город $B$, не принадлежащий второму, и наоборот, во втором есть город $D$, не принадлежащий первому (см. рисунок). Тогда из $A$ можно вылететь в $B$, из $B$ – в $C$, из $C$ – в $D$, из $D$ – в $A$. Тем самым искомая четвёрка городов найдена.
Замечания
Схема авиасообщения, описанная в условии этой задачи, представляет собой пример ориентированного графа. Подробнее о них можно почитать в главах V–VI книги Оре О.
Графы и их применения. – М.: Мир, 1965. Одну из теорем об ориентированных графах из этой книги можно сформулировать так: если в некоторой стране все города попарно соединены рейсами, но только в одном направлении, и из каждого множества городов можно одним из рейсов вылететь в город не из этого множества, то существует циклический маршрут, по которому можно облететь все города страны.
Источники и прецеденты использования
