В некоторой стране из каждого города в любой другой можно проехать, минуя остальные города. Известна стоимость каждого такого проезда. Составлены два маршрута поездки по городам страны. В каждый из этих маршрутов каждый город входит ровно по одному разу. При составлении первого маршрута руководствовались следующим принципом: начальный пункт маршрута выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наименьшую стоимость (если таких городов несколько, то выбирается любой из них); и так до тех пор, пока не будут пройдены все города. При составлении второго маршрута начальный город тоже выбирается произвольно, а на каждом следующем шаге среди городов, через которые маршрут ещё не проходил, выбирается тот, поездка в который из предыдущего города имеет наибольшую стоимость. Докажите, что общая стоимость проезда по первому маршруту не больше общей стоимости проезда по второму маршруту.
А. А. Берзиньш
Всесоюзная математическая олимпиада школьников (XI, 1977 год, 9 класс)
Пусть $a_1$, $a_2$, $\ldots$, $a_{n-1}$ — билеты первого маршрута, $b_1$, $b_2$, $\ldots$, $b_{n-1}$ — билеты второго маршрута ($n$ — число городов). Обозначим стоимость любого билета $c$ через $\textit{Ц}(c)$, а стоимость проезда из города $A$ в город $B$ через $\textit{Ц}(AB)$. Утверждение будет доказано, если нам удастся построить отображение $f\colon\{a_1,{\ldots},a_{n-1}\}\to\{b_1,{\ldots},b_{n-1}\}$, обладающее следующими двумя свойствами:
а) отображение $f$ взаимно однозначно;
б) для любого билета $a$ из первого маршрута $\textit{Ц}(a)\le\textit{Ц}(f(a))$.
Мы укажем способ, по которому строится отображение $f$, обладающее свойством б). Чтобы доказать его взаимнооднозначность, мы покажем, что этот же способ приводит к построению обратного к $f$ отображения $g\colon\{b_1,{\ldots},b_{n-1}\}\to\{a_1,{\ldots},a_{n-1}\}$ — такого, что для любого билета $a$ из первого маршрута $g(f(a))= a$.
Рис. 4. Чёрными стрелками выделены несчастливые билеты, пунктирными голубыми линиями показано соответствие между билетами двух маршрутов.
Способ построения отображения $f$. Пусть $a$ — некоторый билет первого маршрута, взятый в городе $A$. Обозначим через $X_1(A)$ множество городов, которые в первом маршруте встречаются позже $A$, а через $X_2(A)$ — множество городов, встречающихся позже $A$ во втором маршруте. Возможны следующие два случая.
1. $X_1(A)\cap X_2(A)\ne\varnothing$.
В этом случае назовём билет $a$ первого маршрута счастливым и положим $f(a)=b$, где $b$ — билет второго маршрута, купленный в городе $A$ (см. рис. 4, а).
2. $X_1(A)\cap X_2(A)=\varnothing$.
В этом случае назовём билет $a$ первого маршрута несчастливым. Выберем из множества $X_1(A)$ такой город $B\colon B\in X_1(A)$, что $X_1(A)\cap X_2(B)=\varnothing$. Легко понять, что этими двумя условиями город $B$ определяется единственным образом. Действительно, предположив, что существуют два города $B_1$ и $B_2$, такие, что $B_1\in X_1(A)$, $B_2\in X_1(A)$ и $X_1(A) \cap X_2(B_1)=\varnothing$, $X_1(A)\cap X_2(B_2)=\varnothing$, мы получим противоречие: поскольку из условия задачи следует, что для любых двух городов $C$ и $D$ либо $C\in X_2(D)$, либо $D\in X_2(C)$, должно быть либо $B_2\in X_1(A)\cap X_2(B_1)$, либо $B_1\in X_1(A)\cap X_2(B_2)$. Положим теперь $f(a)=b$, где $b$ — билет второго маршрута, купленный в выбранном городе $B$ (рис. 4, б).
Проверим для отображения $f$ выполнение свойства б). Если $a$ — счастливый билет, то $\textit{Ц}(a)\le\textit{Ц}(AC)\le\textit{Ц}(b)$ (здесь $C$ — какой-то город из непустого пересечения множеств $X_1(A)$ и $X_2(A)$). Если же $a$ — несчастливый билет, то $\textit{Ц}(a)\le\textit{Ц}(AB)=\textit{Ц}(BA)\le\textit{Ц}(b)$ (здесь мы воспользовались тем, что стоимости проездов из $A$ в $B$ и из $B$ в $A$ совпадают).
Проверим теперь, что построенное отображение $f$ взаимнооднозначно. Определим билеты первого и второго типов для второго маршрута так же, как это было сделано для билетов первого маршрута. Определим отображение $g$ на множестве билетов второго маршрута правилами, сформулированными в пунктах 1 и 2. Покажем, что так определённое отображение $g\colon\{b_1,{\ldots},b_{n-1}\}\to\{a_1,{\ldots},a_{n-1}\}$ обратно к нашему отображению $f$, т. е. покажем, что для любого билета $a$ первого маршрута $g(f(a))=a$ (рис. 4, в).
Пусть $a$ — счастливый билет первого маршрута (купленный в городе $A$): $X_1(A)\cap X_2(A)\ne\varnothing$. Соответствующий ему по правилу 1 билет $b=f(a)$ второго маршрута (купленный тоже в городе $A$) также счастливый, и по определению отображения $g$ имеем $g(b)=a$. Поэтому в этом случае $g(f(a))=a$.
Пусть теперь $a$ — несчастливый билет первого маршрута. Легко видеть, что соответствующий ему во втором маршруте билет $b=f(a)$, купленный в городе $B$, определяемом условиями $B\in X_1(A)$ и $X_1(A)\cap X_2(B)=\varnothing$, будет несчастливым билетом второго маршрута, поскольку $X_1(B)\subset X_1(A)$ (и, следовательно, $X_1(B)\cap X_2(B)=\varnothing$). Покажем, что правило 2 ставит в соответствие билету $b$ второго маршрута, купленному в городе $B$, билет $a$ первого маршрута, купленный в городе $A$. Для этого нужно убедиться только в том, что $A\in X_2(B)$ (условие $X_2(B)\cap X_1(A)=\varnothing$ у нас выполнено). Действительно, $X_1(A)\cap X_2(A)=\varnothing$ и $B\in X_1(A)$, так что $B\not\in X_2(A)$. Но тогда $A\in X_2(B)$. Поэтому, согласно определению, $g(b)=a$, так что и в этом случае мы получаем $g(f(a))=a$.
