|
|
 |
Условие
В некотором государстве 32 города, каждые два из которых соединены дорогой с односторонним движением. Министр путей сообщения, тайный злодей, решил так организовать движение, что, покинув любой город, в него нельзя будет вернуться. Для этого он каждый день, начиная с 1 июня 2021 года, может менять направление движения на одной из дорог. Докажите, что он сможет добиться своего к 2022 году (то есть за 214 дней).Решение
Докажем общую формулу. Пусть в государстве $2^n$ городов. Тогда министр сможет добиться желаемого не более чем за $2^{n-2}(2^n - n - 1)$ дней.
Лемма. Пусть в государстве $2k$ городов, каждые два из которых соединены дорогой с односторонним движением. Выберем из них половину с наибольшим числом исходящих дорог. Тогда всего из выбранных городов исходит суммарно не менее $k^2$ дорог.
Доказательство. Пусть из $k$ выбранных городов исходит менее $k^2$ дорог, тогда по принципу Дирихле найдется город, из которого исходит не более $k - 1$ дороги. Тогда, так как выбраны города с наибольшим числом исходящих дорог, из каждого из оставшихся $k$ городов исходит также не более $k - 1$ дороги. Суммарно исходит менее $k^2 + k(k-1) = 2k^2 - k$ дорог, при том, что общее число дорог в точности ${\frac{2k(2k-1)}{2}} = 2k^2 - k$. Противоречие, лемма доказана.
Теперь перейдем к доказательству основной формулы. Докажем ее по индукции.
База $n = 1$: между двумя городами только одна дорога и она уже и так в одном направлении. Ничего менять не придется.
Шаг индукции. Пусть для $2^n$ городов утверждение верно. Докажем для $2^{n+1}$. Разделим города на две группы по $2^n$ городов. В первую группу поместим города с наибольшим количеством исходящих дорог. В соответствии с леммой из всех городов этой группы суммарно исходит не менее $2^{2n}$ дорог.
Из этих дорог $\smash[t]{\frac{2^n(2^n - 1)}{2}}$ – дороги внутри группы, поэтому из первой группы во вторую ведет не менее $2^{n-1}(2^n + 1)$ дорог. Тогда из $2^{2n}$ дорог между первой и второй группами в первую направлено не более $2^{n-1}(2^n - 1)$. Не более чем за $2^{n-1}(2^n - 1)$ дней министр направит все эти дороги во вторую группу. И еще не более чем за $2 \cdot 2^{n-2}(2^n - n -1)$ дней он добьется того, чтобы в каждой группе нельзя было выехать из города и в него вернуться. Тогда всего потребуется не более $2^{n-1}(2^{n+1} - n - 2)$ дней.
Так как $32 = 2^5$, то на осуществление желаемого министру потребуется не более $2^3(2^5-5-1) = 208$ дней, что меньше $214$ дней, оставшихся до 2022 года.
