13 городов расположены в разных странах мира. Они соединены между собой авиалиниями, которые принадлежат трем авиакомпаниям. Известно, что если любая из авиакомпаний прекратит полеты, то можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть между этими городами?
update
Первым правильно ответил Дмитрий.Ответ
18 авиалиний. Обозначим число различных авиалиний между городами через x. Если мы уберем одну из них, города могут распасться на две несвязанные группы. После удаления следующей авиалинии не более одной группы распадется еще на две. Продолжая аналогично, получим, что после удаления последней авиалинии количество разрозненных групп не превысит x + 1. Поскольку 13 городов без авиалиний - это 13 групп, то x >= 12. Обозначим количество линий у авиакомпаний через a, b и c. По доказанному, a + b >= 12 , b + c >= 12 , a + c >= 12 . Складывая эти неравенства, получаем 2(a + b + c) >= 36. Следовательно, минимальное значение a + b + c = 18.
Думаю 12
ОтветитьУдалить12 линий смогут соединить 13 городов только последовательно один за другим. И при обрыве одной связи образуется две группы городов. И из одной группы в другую уже нельзя будет попасть. Так что 12 будет мало.
ОтветитьУдалитьКогда одна из авиакомпаний прекратит полеты, между 13-ю городами должно остаться минимум 12 линий на две авиакомпании, чтобы соединить их все.
ОтветитьУдалитьЧтобы не зависеть о выбора авиакомпании, прекратившей полеты, количество линий компаний должно быть одинаково.
Т.е. на каждую авиакомпанию приходится 6 авиалиний, а всего их 18.
18 - это верный ответ.
ОтветитьУдалить