Олимпиада имени Леонарда Эйлера2008-2009 учебный год, I тур заключительного этапа

В стране Леонардии все дороги — с односторонним движением. Каждая дорога соединяет два города и не проходит через другие города. Департамент статистики вычислил для каждого города суммарное число жителей в городах, откуда в него ведут дороги, и суммарное число жителей в городах, куда ведут дороги из него. Докажите, что хотя бы для одного города первое число оказалось не меньше второго. ( Н. Гравин )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение 1. Построим граф, вершины которого соответствуют жителям страны, причём две вершины соединены направленным ребром в том и только том случае, когда их города соединены дорогой (направление на ребре будет такое же, как на дороге между городами). Для каждой вершины $v$ этого графа обозначим через $f(v)$ количество рёбер, входящих в $v$, минус количество рёбер, выходящих из $v$. Сумма $f(v)$ по всем вершинам графа равна 0, так как каждое ребро вносит в нее одну $+1$ и одну $- 1$. Значит, найдется такая вершина $u$, что $f(u) \geq 0$. Остается отметить, что $f(u)$ в точности равно разности первого и второго чисел для города, в котором живет $u$.

Комментарии от администратора Комментарии от администратора №2.     Решение 2. Пусть $n(A)$ — число жителей города $A$, а $f(A)$ — суммарное население городов, дороги из которых входят в $A$, минус суммарное население городов, в которые выходят дороги из $A$. Если утверждение задачи неверно, то $f(A) < 0$ для каждого города $A$. Тогда сумма $S$ чисел $n(A)f(A)$ по всем городам страны отрицательна. С другой стороны, рассмотрим любую дорогу из $A$ в $B$. В число $n(B)f(B)$ эта дорога «вносит вклад» $+n(B)n(A)$, а в число $n(A)f(A)$ — «вклад» $- n(A)n(B)$. Рассмотрев все дороги, получим, что $S = 0$. Противоречие.
Замечание. Отметим, что во втором решении мы использовали лишь тот факт, что «количество жителей города» положительно. Чтобы оно было целым, не требуется.