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

Эйлерии елінде 101 қала бар. Кез келген екі қала 99 авиакомпанияның қандай да бір біреуінің екі бағытты тұра рейсімен қосылған. Әр қаладан барлық 99 авиакомпанияның рейстері шығатыны белгілі. Егер үш қаланың кез келген екеуі қос-қостан бірдей авиякомпания рейсімен қосылса, онда оларды үшбұрыш деп атайық. Эйлерии елінде үшбұрыш саны 1-ден көп емес екенін дәлелдеңіздер. ( И. Богданов, Д. Карпов )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Назовём $\textit{галочкой}$ два рейса одной авиакомпании, выходящие из одного города. Из каждого города выходит ровно 100 рейсов, где представлены все 99 авиакомпаний. Поэтому каждый город служит центром ровно для одной галочки, то есть всего имеется 101 галочка.
      Пусть в Эйлерии есть хотя бы два треугольника. Каждый из них порождает три галочки, принадлежащие одной авиакомпании. Но тогда на долю остальных 97 или 98 авиакомпаний остается максимум 95 галочек. Значит, найдётся авиакомпания, не имеющая галочек, то есть из каждого города выходит ровно по одному рейсу этой компании. Но у каждого рейса два конца, и суммарное количество этих концов не может равняться нечетному числу 101. Противоречие.