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$.

Answer 2

Давайте рассмотрим различные случаи и попробуем минимизировать количество групп.

1. Группы из одного числа: Если каждое число будет отдельной группой, то условие "если в группе хотя бы два числа, то сумма любых двух чисел из группы делится на 8" автоматически выполняется, потому что в группе всего одно число. Таким образом, это удовлетворяет условиям задачи.

2. Группы из двух чисел: Попробуем составить группы по два числа. Однако, чтобы сумма любых двух чисел из группы делилась на 8, числа должны иметь вид $8k$ и $8k + 4$ (где $k$ - целое число). Например, возможные пары: $8 \cdot 1$ и $8 \cdot 1 + 4$, $8 \cdot 2$ и $8 \cdot 2 + 4$, и так далее. Но даже в этом случае у нас получится нечетное число (всегда на 4 больше четного числа), и мы не сможем сформировать группы из двух чисел, удовлетворяющие условиям задачи.

Таким образом, минимальное количество групп - каждое число в своей группе. По числу от 1 до 400 - это 400 групп.

Такое решение гарантирует, что в каждой группе только одно число, и условие "если в группе хотя бы два числа, то сумма любых двух чисел из группы делится на 8" выполняется.