Леонард Эйлер атындағы олимпиада,2008-2009 оқу жылы, қорытынды кезеңнің 1-ші туры

Леонардия елінде барлық жолдар бір бағытты ғана. Әр жол тек екі қаланы қосады және басқа үшінші қала арқылы өтпейді. Статистика департаменті әр қала үшін, сол қалаға басқа қаладан жол кіретін қалалардағы адамдардың жалпы санын және сол қаладан басқа қалаға жол шығатын қалалардағы адамдардың жалпы санын есептеді. Сонда, кемінде бір қала үшін бірінші қосынды екінші қосындыдан кем емес екенін дәлелдеңдер. ( Н. Гравин )

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

Комментарии от администратора Комментарии от администратора №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$. Противоречие.
Замечание. Отметим, что во втором решении мы использовали лишь тот факт, что «количество жителей города» положительно. Чтобы оно было целым, не требуется.