Question

К некотором высокогорном государстве 161 город. Каждый из них соединён с каждым из остальных канатной дорогой с односторонним движением. Причём в каждый город приходит 80 канатных дорог и из каждого города выходит 80 канатных дорог. Докажи, что из каждого города можно добраться до любого другого, проехав не более чем по трём канатным дорогам.
 
Доказательство: рассмотрим два города, назовём их N и K.
Рассмотрим  городов, в которые входят дороги из города N.
И 80 городов, из которых выходят дороги в K.
Так как 80+80
А всего городов осталось 161 −2
Значит, существует город, назовём его S, который принадлежит обоим множествам городов. А это означает, что можно проехать по маршруту N — S — K.

Answer 1

Дано:
В высокогорном государстве 161 город.
Каждый город соединен с каждым другим канатной дорогой с односторонним движением.
В каждый город приходит 80 канатных дорог, и из каждого города выходит 80 канатных дорог.

Найти:
Доказать, что из каждого города можно добраться до любого другого, проехав не более чем по трём канатным дорогам.

Решение:
Рассмотрим два произвольных города N и K. Из города N выходит 80 дорог, и в город K входит 80 дорог. Так как всего городов 161, то остается 161 - 2 = 159 других городов.

Следовательно, существует город S, который принадлежит как множеству городов, в которые входят дороги из города N, так и множеству городов, из которых выходят дороги в город K. Это означает, что можно проехать по маршруту N — S — K, используя не более чем три канатные дороги.

Ответ:
Из каждого города можно добраться до любого другого, проехав не более чем по трём канатным дорогам.