APMO

We claim that $k=2^a$ for all $a\ge 0$. Let $A=\{1,2,4,8,\dots \}$ and $B=\mathbb{N}\backslash A$. For any set $T$, let $s(T)$ denote the sum of the elements of $T$. (If $T$ is empty, we let $s(T)=0$.) We first show that any positive integer $k=2^a$ satisfies the desired property. Let $B^{\prime }$ be a subset of $B$ with $a$ elements, and let $S=A\cup B^{\prime }$. Recall that any nonnegative integer has a unique binary representation. Hence, for any integer $t>s\left(B^{\prime }\right)$ and any subset $B^{\prime \prime }\subseteq B^{\prime }$, the number $t-s\left(B^{\prime \prime }\right)$ can be written as a sum of distinct elements of $A$ in a unique way. This means that $t$ can be written as a sum of distinct elements of $B^{\prime }$ in exactly $2^a$ ways. Next, assume that some positive integer $k$ satisfies the desired property for a positive integer $m\ge 2$ and a set $S$. Clearly, $S$ is infinite.

Lemma: For all sufficiently large $x\in S$, the smallest element of $S$ larger than $x$ is $2x$.

Proof of Lemma: Let $x\in S$ with $x>3m$, and let $x<y<2x$. We will show that $y\notin S$. Suppose first that $y>x+m$. Then $y-x$ can be written as a sum of distinct elements of $S$ not including $x$ in $k$ ways. If $y\in S$, then $y$ can be written as a sum of distinct elements of $S$ in at least $k+1$ ways, a contradiction. Suppose now that $y\le x+m$. We consider $z\in (2x-m,2x)$. Similarly as before, $z-x$ can be written as a sum of distinct elements of $S$ not including $x$ or $y$ in $k$ ways. If $y\in S$, then since $m<z-y<x$, $z-y$ can be written as a sum of distinct elements of $S$ not including $x$ or $y$. This means that $z$ can be written as a sum of distinct elements of $S$ in at least $k+1$ ways, a contradiction. We now show that $2x\in S$; assume for contradiction that this is not the case. Observe that $2x$ can be written as a sum of distinct elements of $S$ including $x$ in exactly $k-1$ ways. This means that $2x$ can also be written as a sum of distinct elements of $S$ not including $x$. If this sum includes any number less than $x-m$, then removing this number, we can write some number $y\in (x+m,2x)$ as a sum of distinct elements of $S$ not including $x$. Now if $y=y^{\prime }+x$ where $y^{\prime }\in (m,x)$ then $y^{\prime }$ can be written as a sum of distinct elements of $S$ including $x$ in exactly $k$ ways. Therefore $y$ can be written as a sum of distinct elements of $S$ in at least $k+1$ ways, a contradiction. Hence the sum only includes numbers in the range $[x-m,x)$. Clearly two numbers do not suffice. On the other hand, three such numbers sum to at least $3(x-m)>2x$, a contradiction. From the Lemma, we have that $S=T\cup U$, where $T$ is finite and $U=\{x,2x,4x,8x,\dots \}$ for some positive integer $x$. Let $y$ be any positive integer greater than $s(T)$. For any subset $T^{\prime }\subseteq T$, if $y-s\left(T^{\prime }\right)\equiv 0(\mathrm{mod}x)$, then $y-s\left(T^{\prime }\right)$ can be written as a sum of distinct elements of $U$ in a unique way; otherwise $y-s\left(T^{\prime }\right)$ cannot be written as a sum of distinct elements of $U$. Hence the number of ways to write $y$ as a sum of distinct elements of $S$ is equal to the number of subsets $T^{\prime }\subseteq T$ such that $s\left(T^{\prime }\right)\equiv y(\mathrm{mod}x)$. Since this holds for all $y$, for any $0\le a\le x-1$ there are exactly $k$ subsets $T^{\prime }\subseteq T$ such that $s\left(T^{\prime }\right)\equiv a(\mathrm{mod}x)$. This means that there are $kx$ subsets of $T$ in total. But the number of subsets of $T$ is a power of $2$, and therefore $k$ is a power of $2$, as claimed.

---

Alternative solution.

Solution 2. We give an alternative proof of the first half of the lemma in the Solution 1 above. Let $s_1<s_2<\cdots$ be the elements of $S$. For any positive integer $r$, define $A_r(x)={\prod }_{n=1}^r\left(1+x^{s_n}\right)$. For each $n$ such that $m\le n<s_{r+1}$, all $k$ ways of writing $n$ as a sum of elements of $S$ must only use $s_1,\dots ,s_r$, so the coefficient of $x^n$ in $A_r(x)$ is $k$. Similarly the number of ways of writing $s_{r+1}$ as a sum of elements of $S$ without using $s_{r+1}$ is exactly $k-1$. Hence the coefficient of $x^{s_{r+1}}$ in $A_r(x)$ is $k-1$. Fix a $t$ such that $s_t>2(m+1)$. Write $$A_{t-1}(x)=u(x)+k\left(x^{m+1}+\cdots +x^{s_t-1}\right)+x^{s_t}v(x)$$ for some $u(x),v(x)$ where $u(x)$ is of degree at most $m$. Note that $$A_{t+1}(x)=A_{t-1}(x)+x^{s_t}{A}_{t-1}(x)+x^{s_{t+1}}{A}_{t-1}(x)+x^{s_t+s_{t+1}}{A}_{t-1}(x)$$ If $s_{t+1}+m+1<2s_t$, we can find the term $x^{s_{t+1}+m+1}$ in $x^{s_t}{A}_{t-1}(x)$ and in $x^{s_{t+1}}{A}_{t-1}(x)$. Hence the coefficient of $x^{s_{t+1}+m+1}$ in $A_{t+1}(x)$ is at least $2k$, which is impossible. So $s_{t+1}\ge 2s_t-(m+1)>s_t+m+1$. Now $$A_t(x)=A_{t-1}(x)+x^{s_t}u(x)+k\left(x^{s_t+m+1}+\cdots x^{2s_t-1}\right)+x^{2s_t}v(x).$$ Recall that the coefficent of $x^{s_{t+1}}$ in $A_t(x)$ is $k-1$. But if $s_t+m+1<s_{t+1}<s_{2t}$, then the coefficient of $x^{s_{t+1}}$ in $A_t(x)$ is at least $k$, which is a contradiction. Therefore $s_{t+1}\ge 2s_t$.