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

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

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

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

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

Так как \(150 + 150\) \(=\) [ ].

А всего городов осталось \(301-2\) \(=\) [ ].

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