В королевстве N городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются соседними). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
  Однажды Король провел такую реформу: каждый из N мэров городов стал снова мэром одного из N городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара соседних городов, обменявшихся мэрами.

   Решение

Темы:    [ Обход графов ] [ Индукция (прочее) ] [ Перестановки и подстановки (прочее) ]

Сложность: 5- Классы: 9,10,11

Прислать комментарий

Условие

  В королевстве N городов, некоторые пары которых соединены непересекающимися дорогами с двусторонним движением (города из такой пары называются соседними). При этом известно, что из каждого города можно доехать до любого другого, но невозможно, выехав из некоторого города и двигаясь по различным дорогам, вернуться в исходный город.
  Однажды Король провел такую реформу: каждый из N мэров городов стал снова мэром одного из N городов, но, возможно, не того города, в котором он работал до реформы. Оказалось, что каждые два мэра, работавшие в соседних городах до реформы, оказались в соседних городах и после реформы. Докажите, что либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара соседних городов, обменявшихся мэрами.

Решение

  Применим индукцию. Утверждение очевидно при  N = 1  и  N = 2. 
  Шаг индукции. Пусть Γ₁ – множество городов, из которых исходит одна дорога, а Γ – множество остальных городов. Начав движение по различным дорогам из некоторого города, согласно условию, мы не сможем попасть дважды в один и тот же город, поэтому когда-нибудь мы закончим движение в городе из множества Γ₁. Это означает, что множество Γ₁ непусто. Ясно, что при  N ≥ 3  множество Γ непусто, и в нем меньше, чем N городов.
  Назовём значимостью мэра количество городов, соседних с городом, где он работает. По условию значимость каждого мэра после реформы не уменьшилась. В частности, мэр города, принадлежащего множеству Γ, после реформы стал мэром некоторого города из множества Γ, то есть в результате реформы в городах множества Γ тоже произошла перестановка мэров. Ясно, что из каждого города  A ∈ Γ  можно доехать до любого другого города  B ∈ Γ,  не заезжая в города множества Γ₁. Поэтому множество городов Γ и реформа, рассмотренная только на городах из Γ, удовлетворяет условию задачи. Применив предположение индукции, получаем, что в множестве Γ либо найдётся город, в котором мэр после реформы не поменялся, либо найдётся пара соседних городов, обменявшихся мэрами, что и требовалось.

Источники и прецеденты использования