Задача. В классе учатся 12
мальчиков. В течение месяца некоторые из них здоровались друг с другом за руку, при этом известно, что всего было совершено 660
рукопожатий. При каком наибольшем k
можно заведомо утверждать, что можно выделить группу из 7
людей, внутри которой было совершено хотя бы k
рукопожатий?
Решение. Рассмотрим все возможные группы из 7
людей, их
...
Пронумеруем эти группы и обозначим через Si
количество рукопожатий, которые были совершены в i
-й группе. Рассмотрим сумму S1+S2+…
, она равна суммарному количеству рукопожатий, совершённых во всех группах. Посчитаем её другим способом. Всего рукопожатий 660
, каждое рукопожатие в сумме S1+S2+…
учитывается
...
раз, поэтому
S1+S2+…=660 ⋅ ...
Следовательно, найдётся Si
, которое не меньше, чем
...
Приведём пример, когда не получится выбрать группу из 7
человек, в которой совершено больше рукопожатий. Несложно видеть, что если любые два человека пожали друг другу руки ...
раз, то в любой компании из 7
человек будет совершено нужное количество рукопожатий.