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