Азиатско-Тихоокеанская математическая олимпиада, 2014 год

Пусть $n$ и $b$ — натуральные числа. Число $n$ назовем $b\,—\it{различимым}$, если существует такое множество из $n$ различных натуральных чисел, меньших $b$, что в нем нет двух различных подмножеств с одинаковой суммой элементов.
(а) Докажите, что число $8$ является $100\,$— различимым.
(б) Докажите, что число $9$ не является $100\,$— различимым. ( Australia )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. (а) Положим $S = \{3,6,12,24,48,95,96,97 \},$ то есть $$S = \{3 \cdot 2^k : 0 \le k \le 5 \} \cup \{3\cdot 2^5-1, 3\cdot 2^5 +1 \}.$$
Когда $k$ пробегает значения от $0$ до $5$, суммы, составленные из чисел $3 \cdot 2^k$ есть $3t$, где $1 \le t \le 63$. Это $63$ делящихся на $3$ числа, не превосходящих $3 \cdot 63 = 189.$
Суммы элементов $S$ также могут быть $95 + 97 = 192$ и всеми числами, являющимися суммами $192$ и сумм, составленных из чисел $3 \cdot 2^k$ с $0 \le k \le 5.$ Это $64$ делящихся на $3$ числа, не меньших $192.$ К тому же, суммами элементов в $S$ могут быть число $95$ и все числа, полученные как сумма $95$ и суммы, составленные из чисел $3 \cdot 2^k$ с $0 \le k \le 5.$ Это $64$ сравнимых с $-1$ по модулю $3$ числа.
Наконец, суммами элементов $S$ являются число $97$ и все числа, полученные как сумма $97$ и суммы, составленные из чисел $3 \cdot 2^k$ с $0 \le k \le 5.$ Это $64$ сравнимых с $1$ по модулю $3$ числа.
Следовательно, существует по крайней мере $63 + 64 + 64 + 64 = 255$ различных сумм, составленных из элементов $S$. С другой стороны, $S$ имеет $2^8 - 1 = 255$ непустых подмножеств. Таким образом, $S$ не имеет двух различных подмножеств с одинаковой суммой элементов, то есть, число $8$ является $100$-различимым.

(б) Предположим, что число $9$ является $100$-различимым. Тогда существует такое множество $S = \{ s_1, \ldots, s_9\}$, $s_i < 100$, что в нем не существует двух различных подмножеств с одинаковой суммой элементов. Пусть $0 < s_1 < \dots < s_9 < 100.$
Пусть $X$ есть множество всех подмножеств $S$, содержащих не менее $3$ и не более $6$ элементов, а $Y$ — множество всех подмножеств $S$, содержащих ровно 2, 3 или 4 элемента, больших чем $s_3$.
Множество $X$ состоит из $$ \binom{9}{3} + \binom{9}{4} + \binom{9}{5} + \binom{9}{6} = 84 + 126 + 126 + 84 = 420 $$ подмножеств $S$. Множеством из $X$ с наибольшей суммой элементов является $\{s_4, \ldots, s_9 \}$, а множеством с наименьшей суммой является $\{s_1, s_2, s_3 \}$. Таким образом, сумма элементов в каждом из $420$ множеств из $X$ есть число от $s_1 + s_2 + s_3$ до $s_4 + \dots + s_9$, количество которых ровно $(s_4 + \dots + s_9) - (s_1 + s_2 + s_3) + 1$. Согласно принципу Дирихле, это означает, что $(s_4 + \dots + s_9) - (s_1 + s_2 + s_3) + 1 \ge 420$, то есть $$ (s_4 + \dots + s_9) - (s_1 + s_2 + s_3) \ge 419. \quad (1) $$ Теперь подсчитаем количество подмножеств в $Y$. Заметим, что $\{s_4, \ldots, s_9 \}$ имеет $\binom{6}{2}$ двухэлементных, $\binom{6}{3}$ трехэлементных и $\binom{6}{4}$ четырехэлементных подмножеств, в то время как $\{s_1, s_2, s_3 \}$ имеет ровно $8$ подмножеств. Следовательно, количество подмножеств $S$ в $Y$ равно $$ 8\left(\binom{6}{2} + \binom{6}{3} + \binom{6}{4} \right) = 8(15 + 20 + 15) = 400. $$ Множество в $Y$ с наибольшей суммой элементов есть $\{s_1, s_2, s_3, s_6, s_7, s_8, s_9 \}$, а с наименьшей — $\{s_4, s_5 \}$. Снова, согласно принципу Дирихле, $(s_1 + s_2 + s_3 + s_6 + s_7 + s_8 + s_9) - (s_4 + s_5) + 1 \ge 400,$ то есть $$ (s_1 + s_2 + s_3 + s_6 + s_7 + s_8 + s_9) - (s_4 + s_5) \ge 399. \quad (2) $$ Складывая (1) и (2), получаем $2(s_6 + s_7 + s_8 + s_9) \ge 818$, откуда следует, что $s_9 + 98 + 97 + 96 \ge s_9 + s_8 + s_7 + s_6 \ge 409,$ то есть $s_9 \ge 118$ — противоречие с условием $s_9 < 100$. Таким образом, $9$ не является $100$-различимым.