суббота, 22 января 2011 г.

Авиалинии

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.

4 комментария:

  1. 12 линий смогут соединить 13 городов только последовательно один за другим. И при обрыве одной связи образуется две группы городов. И из одной группы в другую уже нельзя будет попасть. Так что 12 будет мало.

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

    ОтветитьУдалить