Question

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

Answer 1

Ответ:

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

Следовательно, найдётся Si, которое не меньше, чем (660 ⋅ N) / N = 660.

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

Answer 2

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

Приведем пример, когда не получится выбрать группу из 7 человек, в которой совершено больше рукопожатий. Несложно видеть, что если любые два человека пожали друг другу руки по 1 разу, то в любой компании из 7 человек будет совершено нужное количество рукопожатий. В этом случае, k будет равно 6, так как в группе из 7 человек можно совершить максимум 6 рукопожатий.