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

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

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

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