Loading [MathJax]/jax/output/SVG/jax.js

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


В кружке 42 человека, любые двое из которых имеют среди кружковцев не менее десяти общих друзей. Докажите, что найдутся двое, имеющие среди кружковцев не менее двенадцати общих друзей. ( М. Антипов )
посмотреть в олимпиаде

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

Комментарии от администратора Комментарии от администратора №1.    
Решение. Подсчитаем, сколько пар общих знакомых у каждой пары кружковцев, т. е. сколько в графе знакомств существует циклов длины 4 с этими двумя противоположными вершинами. При этом каждый цикл длины 4 будет учтён дважды, поэтому сумма всех полученных результатов подсчёта будет чётна. Допустим, утверждение задачи неверно. Тогда у каждой пары участников кружка либо 10, либо 11 общих знакомых. В первом случае у них будет 109/2=45, а во втором — 1110/2=55 пар общих знакомых. При этом всего пар участников кружка имеется 4241/2=2141, и получается, что сумма всех результатов подсчёта нечётна как сумма нечётного числа нечётных слагаемых. Противоречие.