Задача из журнала «Квант» (2001 год, 3 выпуск)
Условие
Час назад каждый брат в семье был в ссоре с одинаковым количеством сестер, а каждая сестра – с различным количеством братьев. Сейчас некоторые из них помирились, и каждая сестра в ссоре с одинаковым количеством братьев, а каждый брат – с различным количеством сестер. Сколько сестер и братьев в этой беспокойной семье?
Решение
Обозначим через $n$ количество братьев, через $m$ – количество сестер; пусть до примирения каждый брат был в ссоре с $k$ сестрами. Из условия задачи следует, что $n \leqslant 2$, $m \leqslant 3$ . Сначала докажем несколько вспомогательных утверждений.
$\textbf{1°}. m \leqslant n$.
Пронумеруем сестер по возрастанию количества ссор с братьями. Пусть первая сестра час назад была в ссоре с $a_1$ братьями, вторая – с $a_2$ братьями, $\ldots$, $m$-я – с $a_m$ братьями, причем\begin{equation}\label{m1719_first} a_1\lt a_2\lt\ldots \lt a_m \leqslant n.\end{equation}Поскольку после примирения каждая сестра оставалась в ссоре с одинаковым количеством братьев, то
\begin{equation}\label{m1719_second}1\leqslant a_1.\end{equation}Из $(1)$ и $(2)$ следует утверждение $1°$.
$\textbf{2°}. k \lt m$.
Поскольку $a_i \lt n$ для всех $i \lt m$, то $$nk=\sum\limits_{i=1}^ma_i \lt nm,$$ откуда следует утверждение $2°$.
$\textbf{3°}. k \geqslant n − 1$.
Пронумеруем братьев по возрастанию количества ссор после примирения. Пусть первый брат после примирения остался в ссоре с $b_1$ сестрами, второй брат – с $b_2$ сестрами, $\ldots$, $n$-й брат – с $b_n$ сестрами, причем $$ 0\leqslant b_1 \lt b_2 \lt b_3 \lt \ldots \lt b_n \leqslant k.$$ Сначала получим оценку для суммы $\sum\limits_{i=1}^nb_i$ сверху, для чего выпишем цепочку неравенств $$\begin{equation*}\begin{cases}b_n \leqslant k,\\b_{n-1}\leqslant k-1,\\ \ldots \\b_1\leqslant k-(n-1);\end{cases}\end{equation*}$$отсюда $$\begin{equation}\label{m1719_third}\sum\limits_{i=1}^nb_i\leqslant kn-\frac {n(n-1)}{2}.\end{equation}$$Аналогично получим оценку для суммы $\sum\limits_{i=1}^nb_i$ снизу, для чего выпишем цепочку неравенств $$\begin{equation*}\begin{cases}0 \leqslant b_1,\\1\leqslant b_2,\\ \ldots \\n-1\leqslant b_n;\end{cases}\end{equation*}$$отсюда $$\begin{equation}\label{m1719_forth}\frac{(n-1)n}{2}\leqslant \sum\limits_{i=1}^nb_i.\end{equation}$$Объединяя неравенства $(3)$ и $(4)$, получаем$$\frac{(n-1)n}{2}\leqslant kn-\frac{n(n-1)}{2},$$откуда получаем утверждение $3°$. Результаты $1°$, $2°$, $3°$ запишем в виде цепочки$$n\geqslant m\gt k \geqslant n-1,$$откуда следует $n =m$, $k = n -1$. Для дальнейшего решения нам понадобятся следующие утверждения.
$\textbf{4°}. k \geqslant\dfrac{n+1}{2}$.
Просуммировав цепочку неравенств $$\begin{equation*}\begin{cases}a_m\leqslant n,\\a_m-1\leqslant n-1,\\ \ldots \\a_1\leqslant n-(m-1),\end{cases}\end{equation*}$$находим$$nk =\sum\limits_{i=1}^ma_i\leqslant nm-\frac{m(m-1)}{2}.$$С учетом того, что $n =m$, отсюда и получаем утверждение $4°$.
$\textbf{5°}. k \geqslant\dfrac{n+1}{2}$.
Просуммировав цепочку неравенств $$\begin{equation*}\begin{cases}1\leqslant a_1,\\2\leqslant a_2,\\ \ldots \\m\leqslant a_m,\end{cases}\end{equation*}$$находим$$\frac{m(m+1)}{2}\leqslant\sum\limits_{i=1}^ma_i =nk.$$ С учетом того, что $n =m$, отсюда получаем утверждение $5°$.
Итак, $k = n -1 = \dfrac{n+1}{2}$, откуда $n =3$, $m =3$, $k =2$.
Ситуация до примирения и после примирения показана
на рисунках $1$ и $2$ соответственно (дугами обозначены ссоры).
Итак, в беспокойной семейке $3$ сестры и $3$ брата. Решение единственное.