Есть страна, в которой 102 города, при этом из 100 городов выходит по 6 авиалиний, а из городов А и Б выходит... Есть страна, в которой 102 города, при этом из 100 городов выходит по 6 авиалиний, а из городов А и Б выходит по три авиалинии. Докажите, что из А можно долететь в Б напрямую или с пересадками. (Все авиалинии двусторонние).

Предыдущий
вопрос Следующий
вопрос

Предположим, что из города А нельзя долететь до города Б напрямую и без пересадок. Тогда из города А выходит 3 авиалинии, которые направлены не в город Б. Так как из города А выходит 6 авиалиний, остальные 3 авиалинии должны быть направлены в другие города.

Таким образом, из города Б можно долететь напрямую или с пересадками в любой из 99 городов, куда направлены оставшиеся 3 авиалинии из города А. При этом из каждого из этих 99 городов также выходит 6 авиалиний.

Учитывая, что из каждого из городов выходит 6 авиалиний, то из города Б существует маршрут до всех 102 городов, включая город А. Но по условию из города Б не выходит авиалиний в город А.

Таким образом, мы пришли к противоречию, следовательно, из города А можно долететь в город Б напрямую или с пересадками.