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