Asian Pacific Mathematics Olympiad

We claim that $k=2^{a}$ for all $a \geq 0$.
Let $A=\{1,2,4,8, \ldots\}$ 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'$ be a subset of $B$ with $a$ elements, and let $S=A \cup B'$. Recall that any nonnegative integer has a unique binary representation. Hence, for any integer $t>s\left(B'\right)$ and any subset $B'' \subseteq B'$, the number $t-s\left(B''\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'$ in exactly $2^{a}$ ways.
Next, assume that some positive integer $k$ satisfies the desired property for a positive integer $m \geq 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 \leq 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'+x$ where $y' \in (m, x)$ then $y'$ 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, \ldots\}$ for some positive integer $x$. Let $y$ be any positive integer greater than $s(T)$. For any subset $T' \subseteq T$, if $y-s\left(T'\right) \equiv 0 \pmod{x}$, then $y-s\left(T'\right)$ can be written as a sum of distinct elements of $U$ in a unique way; otherwise $y-s\left(T'\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' \subseteq T$ such that $s\left(T'\right) \equiv y \pmod{x}$. Since this holds for all $y$, for any $0 \leq a \leq x-1$ there are exactly $k$ subsets $T' \subseteq T$ such that $s\left(T'\right) \equiv a \pmod{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.

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 \leq n<s_{r+1}$, all $k$ ways of writing $n$ as a sum of elements of $S$ must only use $s_{1}, \ldots, 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<2 s_{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} \geq 2 s_{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^{2 s_{t}-1}\right)+x^{2 s_{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_{2 t}$, then the coefficient of $x^{s_{t+1}}$ in $A_{t}(x)$ is at least $k$, which is a contradiction. Therefore $s_{t+1} \geq 2 s_{t}$.