Азия-тынық мұхит математикалық олимпиадасы, 1996 жыл

Национальный семейный совет хочет пригласить $n$ супружеских пар для формирования 17 дискуссионных групп на следующих условиях:
(1) все члены каждой группы должны быть одинакового пола;
(2) количество человек в любых двух группах должно различаться не более чем на 1;
(3) в каждой группе должен быть хотя бы один человек;
(4) каждый человек должен быть в какой-нибудь группе.
Найдите все такие $n \leq 1996$, при которых такое разбиение возможно.

Комментарий/решение

$k-$ количечтво мужских групп

В каждой группе либо $m$ либо $m+1$ людей

Б.О.О. $k \geq 9$

$km \leq (17-k)(m+1)$

$(17-2k)(m+1) \geq -k$

$m \geq 1$

$(17-2k)(m+1) = 34-4k+(17-2k)(m-1) \geq -k$

$17-2k<0 \rightarrow (17-2k)(m-1) \leq 0$

$34 \geq 3k \rightarrow k\leq 11$

$k=9,10,11$

$k=11$

$11m\leq 6m+6 \rightarrow m=1 \rightarrow n= 11$

$k=10$

$10m \leq 7m+7 \rightarrow m=1,2 \rightarrow n=10,20$

$k=9$

$9m \leq 8m+8 \rightarrow m= \{ 1, \dots, 8\} \rightarrow n=9, 18, 27, 36, 45 , 54, 63, 72$

Ответ:$n=9, 10, 11, 18, 27, 36, 45 , 54, 63, 72$