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

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

Условие

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


Решение

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

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

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

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

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