Условие:
К некотором высокогорном государстве 151 город. Каждый из них соединён с каждым из остальных канатной дорогой с односторонним движением. Причём в каждый город приходит 75 канатных дорог и из каждого города выходит 75 канатных дорог. Докажи, что из каждого города можно добраться до любого другого, проехав не более чем по трём канатным дорогам.
Доказательство: рассмотрим два города, назовём их № и К.
Рассмотрим городов, в которые входят
дороги из города №.
И 75 городов, из которых выходят дороги в К.
Так как 75 +75=
А всего городов осталось 1512=
Значит, существует город, назовём его Ѕ, который принадлежит обоим множествам городов. А это означает, что можно проехать по маршруту № -S-K.