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