Комбинаторика на Турломе: графы, игры, клетчатые задачи, Дирихле

Заметим, что если в классе ровно человек, который поздоровался со всеми остальными, двое тех, кто поздоровались со всеми остальными, но не друг с другом, трое тех, кто поздоровался со всеми остальными, но не друг с другом, ... человек, которые пожали руку всем остальными, кроме как между собой, то будет ровно рукопожатий. Действительно, во-первых, так что группы такого размера возможны. Во-вторых, в каждой группе каждый ребёнок сделал одинаковое число рукопожатий, а дети из разных групп — разное. Но дети из одной группы как раз не жали друг другу руки, а значит условие задачи выполнено. Наконец, если построить граф знакомств на этих детях, то от полного графа его будет отличать отсутствие внунтренних ребёр в каждой группе. То есть всего рёбер будет

Докажем, что не может быть больше людей, совершивших ровно рукопожатий. Допустим обратное, то есть что имеется хотя бы человек, сделавший ровно рукопожатий. Рассмотрим одно из них. Кроме него имеется всего человек в классе, при этом он совершил рукопожатий и есть ещё человек, который сделали ровно столько же рукопожатий. Тогда по принципу Дирихле, так как найдётся человек, совершивший столько же рукопожатий, и которому он жал руку, что противоречит условию задачи.

Из доказанного утверждения легко понять, что приведённый пример является оптимальным. Докажем строго это утверждение. Для этого упорядочим всех школьников по количеству рукопожатий, которые они совершили, и обозначим количество рукопожатий первого из них (т. е. того, кто соврешил максимальное количество рукопожатий) за , следующего по количеству — за и т. д. Тогда — количества рукопожатий, совершённые школьниками нашего класса.

Заметим, что , просто потому что больше, чем рукопожатий совершить невозможно. Причём если , то по утверждению, доказанному ранее. Далее получаем, что и не больше, чем причём , так как если бы было равно хотя бы то и тоже были бы равны а таких людей по доказанному утверждению может быть не более, чем Аналогично можно доказать, что

Тогда

Но сумма, стоящая справа, равна сумме степеней вершин графа из примера, приведённого выше, а она в два раза больше количества рёбер в графе (так как сумма степеней вершин графа равна удвоенному количеству его рёбер).