ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65063
Тема:    [ Степень вершины ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

Автор: Гравин Н.

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


Решение

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

Источники и прецеденты использования

олимпиада
Название Олимпиада имени Леонарда Эйлера (для 8 классов)
год/номер
Номер 1 (2009 год)
тур
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .