Олимпиада имени Леонарда Эйлера2015-2016 учебный год, I тур заключительного этапа

В стране Эйлерии 101 город. Каждые два города соединены двусторонним беспосадочным рейсом одной из 99 авиакомпаний. Известно, что из каждого города выходят рейсы всех 99 компаний. Назовём $\textit{треугольником}$ три города, попарно соединённых рейсами одной и той же компании. Докажите, что в Эйлерии не больше одного треугольника. ( И. Богданов, Д. Карпов )

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

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