Задача 66147
|
|
 |
Условие
В стране некоторые пары городов соединены односторонними прямыми авиарейсами (между любыми двумя городами есть не более одного рейса). Скажем, что город A доступен для города B, если из B можно долететь в A, возможно, с пересадками. Известно, что для любых двух городов P и Q существует город R, для которого и P, и Q доступны. Докажите, что существует город, для которого доступны все города страны. (Считается, что город доступен для себя.)
Решение
Рассмотрим город A, для которого доступно наибольшее количество городов (если таких несколько – любой из них). Предположим, что некоторый город B недоступен для A. По условию существует город C, для которого A и B доступны. Но тогда для С доступны B, а также все города, доступные для A. Противоречие.
