Задача 79438

Темы:    [ Сочетания и размещения ] [ Доказательство от противного ] [ Связность и разложение на связные компоненты ]

Сложность: 3 Классы: 8,9,10

Условие

Двадцать городов соединены 172 авиалиниями.
Доказать, что, используя эти авиалинии, можно из любого города перелететь в любой другой (быть может, делая пересадки).

Решение

Предположим, что из города A недьзя попасть в город B. Пусть C – какой-то из оставшихся 18 городов. Тогда по крайней мере одна их двух авиалиний A–C, B–C отсутствует. Итого из     возможных авиалиний отсутствуют не менее 19 (считая линию A–B), то есть линий не больше 171. Противоречие.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	46
Год	1983
вариант
Класс	9
задача
Номер	4