Областная олимпиада по математике, 2008 год, 9 класс

В стране 100 дорог (каждая дорога соединяет ровно два города и на дорогах двустороннее движение). Известно, что из любых трех дорог можно выбрать две, которые не выходят из одного города. Докажите, что найдутся 40 дорог, никакие две из которых не выходят из одного города.

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

Очевидно 3 дороги с одного города выходить не могут, если иначе то противоречило условию. Значит степень вершины каждого города не больше 2. Давайте выкинем не нужные города(т.е у которых степень вершины 0, они на решение не влияют). Пусть у нас всего городов n. k из них у которых степень вершины 1. Значит n-k у которых степень вершины 2. Тогда верно равенство $2(n-k)+k=200 => 2n-k=200$. Предположим, что не найдутся таких 40 дорог. С городов, у которых степень вершины 1, можно взять не менее $\dfrac{k}{2}$. А с городов у которых степень вершины 2, можно взять не менее $\dfrac{n-k}{2}$. И какое-то из этих выражений меньше 20 и какое-то меньше 40 $=>(i) k <40, n-k<80 => 2(n-k)+k<160+40=200$. Противоречие $(ii)k<80, 2(n-k)<40 => 2(n-k)+k<120<200$. Противоречие.