Разделы 
Дополнительно
Задача по математике - 3384
2019-06-03 
В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?
Решение:
Докажем, что меньше, чем 21 авиалинией не обойтись. Вначале заметим, что если 15 городов соединены авиалиниями так, что можно добраться от любого города до любого другого, то авиалиний не меньше 14. Действительно, вылетим из произвольного города, и попробуем объехать все остальные, при этом, посещение каждого следующего города будет требовать не менее одной новой авиалинии.
Обозначим количество линий у авиакомпаний через $a, b$ и $c$. По доказанному, у любых двух компаний вместе не менее 14 линий, т. е. $a + b \geq 14, b + c \geq 14, c + a \geq 14$. Складывая эти неравенства, получаем: $2 (a + b + c) \geq 42$, т. е. у трех компаний в сумме не менее 21 авиалинии.
Осталось привести пример с 21 авиалинией. Два таких примера показаны на рис.
Ответ: 21 авиалиния.
В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?
Решение:
Докажем, что меньше, чем 21 авиалинией не обойтись. Вначале заметим, что если 15 городов соединены авиалиниями так, что можно добраться от любого города до любого другого, то авиалиний не меньше 14. Действительно, вылетим из произвольного города, и попробуем объехать все остальные, при этом, посещение каждого следующего города будет требовать не менее одной новой авиалинии.
Обозначим количество линий у авиакомпаний через $a, b$ и $c$. По доказанному, у любых двух компаний вместе не менее 14 линий, т. е. $a + b \geq 14, b + c \geq 14, c + a \geq 14$. Складывая эти неравенства, получаем: $2 (a + b + c) \geq 42$, т. е. у трех компаний в сумме не менее 21 авиалинии.
Осталось привести пример с 21 авиалинией. Два таких примера показаны на рис.
Ответ: 21 авиалиния.
