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

Найдите все натуральные $k$, для которых существует натуральное $m$ и множество $S$, состоящее из натуральных чисел, такие, что каждое целое $n > m$ может быть представлено в виде суммы различных элементов из $S$ ровно $k$ способами.

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

Докажем, что $k = 2^\alpha, \forall \alpha \geq 0$. Пусть $A = \{1,2,...,\}$. Пусть $S$ состоит из $A$ и $\alpha$ первых нечетных чисел, кроме $1$. Тогда беря $m=\alpha^2+2\alpha$, получаем требуемое. Так как каждое число можно представить ровно одним способом в виде суммы степеней двойки, а количество способов выбрать несколько нечётных чисел участвующих в сумме ровно $2^\alpha$.

Теперь предположим, что какой-то $k$ удовлетворяет условию задачи. Очевидно, что $S$ бесконечное множество чисел.

Лемма. Для достаточно большого $x \in S$, наименьший элемент в $S$ больший $x$ это $2x$.

Пусть $x \in S, x > 3m$. и $x < y < 2x$. Покажем, что $y \notin S$. Если $y > x+m$, тогда $y-x$ может быть представлено в виде суммы элементов $S$ без $x$ ровно $k$ способами. Если $y \in S$, тогда $y$ может быть представлено в виде суммы элементов $S$ не менее чем $k+1$ способом. Если $y \leq x+m$. Пусть $z \in (2x-m, 2x)$ Аналогично $z-x$ может быть представлено в виде суммы элементов $S$ без $x$ ровно $k$ способами. Так как $m< z-y < x$, то $z-y$ может быть представлено в виде суммы элементов $S$ без $x$ и $y$ ровно $k$ способами. Тогда $z$ представимо в виде суммы элементов $S$ не менее чем $k+1$ способом.

Теперь покажем, что $2x \in S$. Заметим, что $2x$ может быть представлен в виде суммы элементов $S$ включая $x$ ровно $k-1$ способами. Тогда $2x$ может быть представлен в виде суммы элементов $S$ без $x$. Если эта сумма включает число меньшее чем $x-m$, тогда уберя это число, получим, что $y \in (x+m, 2x)$ представимо виде суммы элементов $S$ без $x$. Пусть $z = y-x$, тогда $z \in (m, x)$, значит $z$ может быть представлено в виде суммы элементов $S$ без $x$ ровно $k$ способами. Значит $y$ представимо в виде суммы элементов $S$ не менее чем $k+1$ способом. Тогда в сумме все элементы из интервала $[x-m, x)$. Сумма двух чисел меньше $2x$, а трех $3(x-m) > 2x$. Значит $2x \in S$.

Из леммы получается, что $S = A \cup B$, где $A$ конечное множество, а $B = \{x, 2x, 4x, .....\}$ для $x \in \mathbb{N}$. Пусть $y > sum(A)$, где $sum(X)$ сумма элементов $X$ Для $\forall C \in A$, если $y-sum(C) \equiv 0 \pmod{x}$, то $y-sum(C)$ может быть представлено в виде суммы элементов $B$ одним способом, в противном случае не может быть представлено. Тогда количество способов представить $y$ это количество подмножеств таких, что $y \equiv sum(C) \pmod{X}$. Так как это выполняется для любого $y$, то $\forall \, 0 \leq a \leq x-1$, есть ровно $k$ подмножеств $C \in B$ таких, что $a \equiv sum(C) \pmod{x}$. Это означает что всего $kx$ подмножеств у $B$. Так как количество подмножеств степень двойки, то $k$ - степень двойки.