Покори Воробьёвы горы! 2021, 9 класс, задача 4
Английский клуб посещают джентльменов. Некоторые из них знакомы (знакомства взаимные, т.е. если знает , то и знает ). Известно, что в клубе нет трех попарно знакомых между собой джентльменов.
Однажды джентльмены пришли в клуб, и каждая пара знакомых пожала друг другу руки (один раз). Какое наибольшее число рукопожатий могло быть сделано?
Ответ: рукопожатий.
Решение. Выберем джентльмена, имеющего наибольшее количество знакомых (если таких несколько - выберем любого). Допустим, он имеет знакомых. Эти знакомые не могут быть попарно знакомы между собой. Рассмотрим оставшихся джентльменов, каждый из них имеет не более знакомых, значит количество рукопожатий, которые они сделают не превосходит . Значит общее число не превосходит . Это число максимально, когда . Можно показать, что рукопожатий возможно - разбив джентльменов на группы по человек и чтобы каждый из -й группы был знаком с каждым из второй (а внутри групп знакомств не было).