Математикадан облыстық олимпиада, 2007-2008 оқу жылы, 9 сынып

Бір елдің қалалары жалпы саны 100 жолмен қосылған (әрбір жол дәл екі қаланы қосады және әрбір жолмен екі бағытта да жүруге болады). Кез келген үш жолдың ішінен бір қаладан шықпайтын екі жол таңдап алуға болатыны белгілі. Берілген 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$. Противоречие.