Заполни пропуски в доказательстве задачи.

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

Доказательство: рассмотрим два города, назовём их N и K.

Рассмотрим 90 городов, в которые входят дороги из города N.

И 90 городов, из которых выходят дороги в K.

Так как \(90 + 90\) \(=\) 180.

А всего городов осталось \(181-2\) \(=\) 179.

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