Задача №15474

В группе поровну юношей и девушек. Юноши отправляли электронные письма девушкам. Каждый юноша отправил или 5 писем, или 16 писем, причём и тех и других юношей было не меньше двух. Возможно, что какой-то юноша отправил какой-то девушке несколько писем.

а) Могло ли оказаться так, что каждая девушка получила ровно 7 писем?

б) Какое наименьшее количество девушек могло быть в группе, если известно, что все они получили писем поровну?

в) Пусть все девушки получили попарно различное количество писем (возможно, какая-то девушка не получила писем вообщ

е). Каково наибольшее возможное количество девушек в такой группе?

Пусть количество юношей (и девушек) равно $n\text{,}$ из них $x$ юношей отправили по 5 писем, $y$ — по 16 писем, $x+y=n\text{,}$ $x⩾2\text{,}$ $y⩾2\text{.}$ Всего отправлено писем: $5x+16y\text{.}$

а) Если каждая девушка получила ровно 7 писем, то $5x+16y=7n\text{.}$ Подставляя $n=x+y\text{,}$ получаем:

$$5x+16y=7(x+y)\Rightarrow 9y=2x\Rightarrow x=\frac{9y}{2}.$$

При $y=2$ получаем $x=9\text{,}$ $n=11\text{.}$ Общее число писем $5\cdot 9+16\cdot 2=77\text{,}$ $77/11=7\text{.}$ Распределение возможно (например, каждый юноша отправляет письма произвольно, а затем письма перераспределяются между девушками).

Ответ: да.

б) Пусть все девушки получили по $k$ писем. Тогда $5x+16y=kn\text{,}$ $n=x+y\text{.}$ Отсюда:

$$(k-5)x=(16-k)y,\text{поэтому}\frac{x}{y}=\frac{16-k}{k-5}.$$

Поскольку $x$ и $y$ — натуральные не меньше 2, величина $\frac{16-k}{k-5}$ должна быть положительной и рациональной, причём $5<k<16\text{.}$

Пусть $x=(16-k)t\text{,}$ $y=(k-5)t\text{,}$ $t\in \mathbb{N}\text{.}$ Тогда $n=11t\text{.}$

Минимальное $n$ при условии $x⩾2\text{,}$ $y⩾2$ достигается при $t=1$ и $k$ от 7 до 14 (например, $k=7\text{,}$ $x=9\text{,}$ $y=2\text{,}$ $n=11$). При $k=6$ или $k=15$ требуется $t⩾2\text{,}$ что даёт $n⩾22\text{.}$

Следовательно, наименьшее количество девушек равно 11.

в) Пусть девушки получили попарно различные количества писем: $0,1,\dots ,n-1\text{.}$ Их сумма равна $\frac{n(n-1)}{2}\text{.}$ Это должно равняться $5x+16y=16n-11x$ (так как $y=n-x$).

Получаем уравнение:

$$16n-11x=\frac{n(n-1)}{2}\Rightarrow 32n-22x=n^2-n\Rightarrow n^2-33n+22x=0\Rightarrow 22x=n(33-n).$$

Отсюда $n(33-n)$ должно делиться на 22. Также $x=\frac{n(33-n)}{22}$ должно удовлетворять $2⩽x⩽n-2\text{.}$

Перебором $n$ от 19 до 30 (из неравенств $5n+22⩽\frac{n(n-1)}{2}⩽16n-22$) находим, что только при $n=22$ получаем целое $x\text{:}$ $22\cdot 11=242\text{,}$ $x=242/22=11\text{,}$ $y=11\text{.}$

Проверяем условия: $x=11⩾2\text{,}$ $y=11⩾2\text{.}$ Сумма писем: $5\cdot 11+16\cdot 11=231\text{,}$ что равно $0+1+\cdots +21=231\text{.}$ Распределение возможно (например, можно подобрать матрицу рассылки). Больше $n$ не позволяет ограничение сверху на сумму писем.

Ответ: 22.