Задача 6.
В стране 100 городов. Между любыми двумя городами либо нет соединения, либо налажено авиасообщение, либо есть железная дорога (одновременно и авиасообщения, и железной дороги быть не может). Известно, что если два города соединены с третьим железной дорогой, то между ними есть авиалиния, а если два города соединены с третьим авиалиниями, то между ними есть железная дорога.
Из-за стихийного бедствия отменили все авиарейсы в стране. Правительство постановило в некоторых городах разместить центры гуманитарной помощи, причём так, чтобы из каждого города можно было добраться в подобный центр. Докажите, что необходимо открыть хотя бы 20 таких центров.
Ответ на Задачу 6.
Решение:
Заметим, что никакой город не соединён железной дорогой более чем с двумя другими городами. Действительно, пусть какие-то три города соединены железной дорогой с одним. Тогда все они между собой соединены авиалиниями, что невозможно по условию задачи. Значит, каждый город связан железной дорогой не более чем с двумя другими. Тогда связанные друг с другом железнодорожным сообщением города представляют собой цепочку (возможно, замкнутую). Докажем, что каждая такая цепочка содержит не более 5 вершин.
Пусть города $A$, $B$, $C$, $D$ и $E$ стоят последовательно в цепочке. Поскольку $A$ и $C$ соединены с $B$ железными дорогами, между $A$ и $C$ существует авиалиния. Аналогично между $C$ и $E$ существует авиалиния. Тогда между $A$ и $E$ существует железная дорога, и, значит, города соединены по кругу и больше ни с каким другим городом не связаны. Таким образом, в каждой цепочке не более 5 городов. Чтобы из каждого города можно было добраться до гуманитарного центра, его необходимо открыть в каждой такой цепочке. А значит, и центров необходимо построить хотя бы 100 : 5 = 20, что и требовалось доказать.
