13 городов расположены в разных странах мира. Они соединены между собой авиалиниями, которые принадлежат трем авиакомпаниям. Известно, что если любая из авиакомпаний прекратит полеты, то можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть между этими городами?
update
Первым правильно ответил Дмитрий.Ответ
Думаю 12
ОтветитьУдалить12 линий смогут соединить 13 городов только последовательно один за другим. И при обрыве одной связи образуется две группы городов. И из одной группы в другую уже нельзя будет попасть. Так что 12 будет мало.
ОтветитьУдалитьКогда одна из авиакомпаний прекратит полеты, между 13-ю городами должно остаться минимум 12 линий на две авиакомпании, чтобы соединить их все.
ОтветитьУдалитьЧтобы не зависеть о выбора авиакомпании, прекратившей полеты, количество линий компаний должно быть одинаково.
Т.е. на каждую авиакомпанию приходится 6 авиалиний, а всего их 18.
18 - это верный ответ.
ОтветитьУдалить