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