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

Ответ: 21 авиалиния.

Объяснение. Если одна авиакомпания прекратит полёты, то рейсы двух оставшихся компаний всё равно должны соединять все 15 городов. Чтобы соединить 15 городов, нужно как минимум \(15 - 1 = 14\) авиалиний.

Пусть всего авиалиний \(M\). Для каждой из трёх компаний после её удаления остаётся не меньше 14 линий. Значит:

\[ M - a \ge 14,\quad M - b \ge 14,\quad M - c \ge 14 \]

Если сложить эти неравенства, получим:

\[ 2M \ge 42 \]

\[ M \ge 21 \]

Такое количество возможно: можно распределить линии так, чтобы у каждой компании было по 7 линий, а любые две компании вместе давали дерево из 14 линий, соединяющее все 15 городов.

Значит, наименьшее количество авиалиний — 21.

0 0 Пожаловаться