ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 105148
Темы:    [ Связность и разложение на связные компоненты ]
[ Деревья ]
[ Подсчет двумя способами ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трём авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из каждого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?


Решение

  Обозначим количество линий у авиакомпаний через a, b и c. Если мы закроем последние c авиалиний, то граф останется связным, поэтому  a + b ≥ 14  (см. задачу 31098 г). Аналогично,  b + c ≥ 14,  c + a ≥ 14.  Складывая эти неравенства, получаем:  2(a + b + c) ≥ 42,  то есть у трёх компаний в сумме не менее 21 авиалинии.
  Осталось привести пример с 21 авиалинией. Годится любой из примеров, показанных на рисунках.


Ответ

21 авиалиния.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 66
Год 2003
вариант
Класс 8
задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .