Question

Числа от 1 до 400 разбиты на несколько групп. Известно, что если в группе хотя бы два числа, то сумма любых двух чисел из группы делится на 8. Какое наименьшее количество групп может быть?
Полное решение!!!

Answer 1

Надо заметить, что если в группе хотя бы три числа, то все они должны давать либо остатки $4$ при делении на $8$, либо все делиться на $8$. Если не делятся на восемь, то $a\equiv -b,\; b\equiv -c,\; c\equiv -a \Rightarrow c\equiv b \Rightarrow c\equiv b \equiv 4\equiv a$.

Если в группе два числа, то их остатки могут быть любыми, лишь бы их сумма делилась на восемь.

Понятно, что наиболее выгодно брать большие группы, потому (пока рассуждаем нестрого) определим в одну большую группу все числа, дающие остаток $4$. Таких всего $50$. Делящихся на $8$ тоже $50$. Остается $300$ чисел. Их уже можно разбить только парами (или по одному), а потому получаем $150$ групп. Итого $152$ группы.

Теперь докажем, что меньшее количество групп выделить нельзя. Пусть $s_{\geq 3}$ -- это количество групп, в которых хотя бы три числа, а $s_{2},\;s_{1}$ -- количества групп, где два и одно число соответственно. Пусть $s_{1}$ и $s_{2}$ заданы. Тогда если $s_{3} = 0$, то $s_{1}+2s_{2}=400$ и $s_{1}+s_{2} = 400-s_{2} \stackrel{s_{2}\leq 200}{\geq}200$, что больше предъявленного ранее примера. Пусть $s_{3}=1$. Максимальное число элементов в такой группе равно $50$. Тогда $s_{1}+2s_{2} = 350 \Rightarrow s_{1}+s_{2} = 350-s_{2} \stackrel{s_{2}\leq 175}{\geq} 175$. Наконец, если $s_{3}\geq 2$, то суммарное количество чисел в таких группах не может превосходить $100$. Тогда $s_{1}+2s_{2} = 300 \Rightarrow s_{1}+s_{2} = 300-s_{2} \stackrel{s_{2}\leq 150}{\geq} 150$, следовательно, $s_{1}+s_{2}+s_{3}\geq 152$.