В группе поровну юношей и девушек. Юноши отправляли электронные письма девушкам. Каждый юноша отправил или 5 писем, или 16 писем, причём и тех и других юношей было не меньше двух. Возможно, что какой-то юноша отправил какой-то девушке несколько писем.
а) Могло ли оказаться так, что каждая девушка получила ровно 7 писем?
б) Какое наименьшее количество девушек могло быть в группе, если известно, что все они получили писем поровну?
в) Пусть все девушки получили попарно различное количество писем (возможно, какая-то девушка не получила писем вообще). Каково наибольшее возможное количество девушек в такой группе?
Задание с развёрнутым ответом. Запишите решение и сравните его с разбором.
Ответ: а) да; б) 11; в) 31.
Решение
Пусть юношей и девушек по $n$. Пусть $q$ юношей отправили по 16 писем, а остальные $n-q$ — по 5. В каждой из этих групп не меньше двух:
$$
2\le q\le n-2.
$$
Общее число писем:
$$
T=16q+5(n-q)=16q+5n-5q=5n+11q.
$$
Повторные письма одной девушке разрешены. Значит, для распределения достаточно совпадения общей суммы: можно последовательно назначить адресатов всем отправленным письмам, выдавая каждой девушке нужное количество. Дополнительных ограничений на пары отправитель–получатель нет.
а) Если каждая получила по 7 писем, всего писем $7n$. Приравниваем:
$$
5n+11q=7n;\qquad11q=2n.
$$
Подойдут $q=2,n=11$. Тогда девять юношей отправят по 5 и двое по 16:
$$
9\cdot5+2\cdot16=45+32=77=11\cdot7.
$$
Обе группы юношей содержат хотя бы двух, каждой из 11 девушек можно выделить по 7 писем. Ответ: да.
б) Пусть каждая девушка получила целое число $h$ писем. Тогда:
$$
5n+11q=hn;\qquad11q=(h-5)n.
$$
Значит, $11q$ делится на $n$. Если $n<11$, число $n$ не содержит простой множитель 11. Все его множители, необходимые для делимости $11q$ на $n$, должны тогда содержаться в $q$; поэтому $q$ делится на $n$. Но $2\le q\le n-2<n$, что невозможно. При $n=11$ пример пункта а) подходит. Минимум — 11 девушек.
в) Для $n$ попарно различных неотрицательных количеств наименьший набор $0,1,\ldots,n-1$. Его сумма равна $n(n-1)/2$: при попарном сложении начала и конца каждая пара имеет сумму $n-1$. Поэтому писем должно быть хотя бы $n(n-1)/2$.
С другой стороны, если бы все юноши отправляли по 16, было бы $16n$ писем. Как минимум двое отправили только по 5, то есть на $16-5=11$ меньше каждый. Значит:
$$
\frac{n(n-1)}2\le T\le16n-22.
$$
Умножим на 2 и перенесём всё влево:
$$
n^2-n\le32n-44;\qquad n^2-33n+44\le0.
$$
При $n\ge32$ левая часть положительна, поскольку:
$$
n^2-33n+44=(n-32)(n-1)+12\ge12>0.
$$
Таким образом, $n\le31$. Проверим 31: двое юношей отправят по 5, остальные 29 — по 16:
$$
T=2\cdot5+29\cdot16=10+464=474.
$$
Девушки могут получить $0,1,2,\ldots,29,39$ писем — всего $30+1=31$ различное количество. Проверка суммы:
$$
0+1+\ldots+29+39=\frac{29\cdot30}{2}+39=435+39=474.
$$
Распределение возможно по объяснённому принципу назначения адресатов. Ответ: а) да; б) 11; в) 31 девушка.