К некотором высокогорном государстве 181 город. Каждый из них соединён с каждым из остальных канатной дорогой с односторонним движением. Причём в каждый город приходит 90 канатных…
К некотором высокогорном государстве 181 город. Каждый из них соединён с каждым из остальных канатной дорогой с односторонним движением. Причём в каждый город приходит 90 канатных дорог и из каждого города выходит 90 канатных дорог. Докажи, что из каждого города можно добраться до любого другого, проехав не более чем по трём канатным дорогам. Доказательство: рассмотрим два города, назовем их N и K. Рассмотрим городов, в которые входят дороги из города N. И 90 городов, из которых выходят дороги в к. Так как 90 + 90 = А всего городов осталось 181 - 2 = Значит, существует город, назовём его S, который принадлежит обоим множествам городов. А это означает, что можно проехать по маршруту N - S - К.
Рассмотрим данную конфигурацию как ориентированный граф на 181 вершине (города): между любыми двумя городами существует ровно одна дуга, и для каждого города. // В этом графе вхождение и выход в каждом городе равны по 90.
Возьмём произвольные города N и K.
- Если существует дорога N → K, то путь из N в K имеет длину 1, что удовлетворяет условию.
- Пусть дороги N → K нет. Тогда K → N.
Определим множества:
- A = { города X ≠ N : N → X }, то есть из N уходят дороги в X. По условию |A| = 90.
- B = { города Y ≠ K : Y → K }, то есть в K входят дороги от Y. По условию |B| = 90.
Заметим, что A и B являются подмножествами V \ {N} и V \ {K} соответственно. Так как N ≠ K, получаем, что A ∩ B ⊆ V \ {N, K}, и поэтому |V \ {N, K}| = 181 − 2 = 179.
По принципу включения-исключения: |A ∩ B| = |A| + |B| − |A ∪ B| ≥ 90 + 90 − 179 = 1.
Следовательно, существует город S, который одновременно принадлежит A и B, то есть N → S и S → K. Это даёт путь N → S → K длиной 2.
Итак, для любых двух городов N и K существует маршрут из N в K длиной не более чем по трём канатным дорогам (на самом деле длина не более 2). Доказано.
