Question

Подобно поясните как заполнить пропуски, заполненные пропуски без пояснений не принимаются

Answer 1

Ответ:

Рассмотрим все возможные группы из 7 людей, их 792. Пронумеруем эти группы и обозначим через $S_i$ количество рукопожатий, которые были совершены в i-й группе. Рассмотрим сумму $S_1+S_2+\dots$, она равна суммарному количеству рукопожатий, совершённых во всех группах. Посчитаем её другим способом. Всего рукопожатий 660, каждое рукопожатие в сумме $S_1+S_2+\dots$ учитывается 252 раза, поэтому

$S_1+S_2+\dots=660\cdot 252$

Следовательно, найдётся $S_i$, которое не меньше, чем 210.

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

Пошаговое объяснение:

1. Количество различных групп размера k, которые можно сформировать из n вариантов, можно записать как биномиальный коэффициент из n по k:

$\displaystyle C_n^k=\binom{n}{k}=\frac{n!}{k!(n-k)!}$

В первый пропуск предлагают поставить количество групп, в которые входят семеро из 12, их

$\displaystyle C_{12}^7=\binom{12}{7}=\frac{12!}{7!5!}=\frac{12\cdot11\cdot10\cdot9\cdot8}{1\cdot2\cdot3\cdot4\cdot5}=792$

2. Посчитаем, в какое количество групп входит одно выбранное рукопожатие. В этих группах два места заняты, а остальные 5 могут быть выбраны произвольно из оставшихся 10 вариантов. Это можно сделать

$\displaystyle C_{10}^5=\binom{10}5=\frac{10\cdot9\cdot8\cdot7\cdot6}{1\cdot2\cdot3\cdot4\cdot5}=252$

способами.

3. Если каждое рукопожатие учтено 252 раза, а всего рукопожатий 660, то сумма равна 660 · 252.

4. Так как 660 · 252 : 792 = 210, то обязательно найдется группа, в которой не меньше 210 рукопожатий. Если бы это было не так и в каждой группе было бы меньше 210 рукопожатий, то общее количество рукопожатий во всех группах было бы меньше, чем 210 · 792 = 660 · 252. (Рассуждение выше можно было бы заменить на "по принципу Дирихле")

5. Если в группе из 7 человек каждый пожал руку каждому 1 раз, суммарно в этой группе будет

$\displaystyle C_7^2=\binom{7}{2}=\frac{7\cdot 6}2=21$

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

$\displaystyle 10C_{12}^2=10\binom{12}2=\frac{10\cdot12\cdot11}2=660.$

Таким образом, нельзя гарантировать, что найдется группа, в которой было хотя бы 211 рукопожатий.