This problem was proposed by Warut Suksompong, Thailand

Here is a patched version from what I submitted during the contest. In the contest I messed up the bound $a_1+a_2+\hdots+a_n<2a_{n+1}$ but fortunately I have written the first lemma, hence I got a 5. All powers of two (including $1$) works. $2^t$ is clearly satisfied by the following set $$S = \{3, 3\cdot 2, 3\cdot 2^2,\hdots,3\cdot 2^{t-1}\}\cup\{1,2,2^2,2^3,\hdots\}.$$The harder part is to show that $k$ must be power of two. To do this, we first adjust $m$ to be minimal (i.e. number of ways to represent $m$ is not equal to $k$). Enumerate $S=\{a_1<a_2<a_3<\hdots\}$. First, we make a somewhat long preparation (which you are recommended to skip first) by proving the following bounds. Claim: For any $n$, we have $(a_1+a_2+\hdots+a_n)+2^m \geq \frac{2^n}{k} \geq a_{n+1}-m$ Proof: Simply double-counting representations which is subset of $\{a_1,a_2,\hdots,a_n\}$ It must be a subset of all representations of $0,1,2\hdots,a_1+a_2+\hdots +a_n$. There are at most $2^m$ representations of $0,1,2,\hdots,m$ while each of $m+1,m+2,\hdots,a_1+a_2+\hdots+a_n$ have exactly $k$ of them, hence the left inequality is true. On the other hand, these representations must cover all representations of $m+1,m+2,\hdots,a_{n+1}$. There are exactly $k$ of these hence the right inequality is true. Hence both inequalities are true. $\blacksquare$ The corollary above is the following estimate, which will be critical. Claim: $a_1+a_2+\hdots+a_n<2a_{n+1}$ for all sufficiently large $n$. Proof: Direct computation. First, we note that $a_n\leq\tfrac{2^{n-1}}{k}+m$ from above. Thus $$a_n\geq \left(\frac{2^n}{k}-2^m\right) - \sum_{i=1}^n \left(\frac{2^{i-1}}{k} - m\right) = \frac{2^{n-1}}{k} - mn - 2^m$$Hence we have $$a_1+a_2+\hdots + a_n \leq \sum_{i=1}^n\left(\frac{2^{i-1}}{k} - m\right) = \frac{2^n-1}{k} - mn \leq a_{n+1} + O(n)$$since $a_n\gg n$, the bound holds for all sufficiently large $n$. $\blacksquare$ After preparations above, we present the crux of this problem, which is to show that $S$ is essentially forced. Claim: For all sufficiently large $n$, we have $a_{n+1}=a_1+a_2+\hdots+a_n-m$ Proof: The proof takes two steps. Assume that $a_{n+1}>a_1+a_2+\hdots a_n-m$. Then any representations of $m$ bijectively correspond to any representation of $a_1+a_2+\hdots+a_n-m$ by taking complement from $\{a_1,a_2,\hdots,a_n\}$. Hence $m$ can be represented in exactly $k$ ways, contradiction to minimality. Assume that $a_1+a_2+\hdots+a_n-m>a_{n+1}$. Then above estimates imply $a_1+a_2+\hdots+a_n<2a_{n+1}$. Thus any representations of $a_1+a_2+\hdots+a_n-a_{n+1}$ must bijectively correspond to any representation of $a_{n+1}$, apart from the trivial $\{a_{n+1}\}$ (by taking complement from $\{a_1,a_2,\hdots,a_n\}$). But the former has $k$ while the latter has $k-1$ representations, hence contradiction. $\blacksquare$ From the claim, we get $a_{n+t} = 2^t(a_1+a_2+\hdots+a_n-m)$ for a large $n$. But from our estimate, $a_1+a_2+\hdots+a_n-m = \tfrac{2^n}{k}$. Thus $k\mid 2^n$ or $k$ is a power of two.

i take it back i'm okay with having geo 3 as long as there's p>1 geo

The point is last year's P3 is far too hard for its position. In my opinion this is comparable to IMO P3/6 geometry and should be placed as P5 instead.

@above aren't p5s usually imo 2 level....?

Very nice problem! Let $sum(T)$ denote the sum of elements of a set $T$ (if $T$ is empty then $sum(T) = 0$). We prove that the answer is $k=2^m$ for all integers $m \ge 0$. To show that all $k=2^m$ works, we take $S = \{3^{1}, 3^{2}, ..., 3^{m}\} \cup \{2^{0}, 2^{1}, 2^{2}, ...\}$. For any integer $z > 3^{m+1000}$, the number $z - sum(T)$ can be written using powers of $2$ in exactly one way for any subset $T$ of $S$. Thus, there are exactly $2^m$ ways to write $z$ in terms of distinct elements in $S$. Now, we show that $k$ must be a power of $2$. Call a set of integers $A = \{a_1, a_2, a_3, ...\}$ with $a_{i} < a_{i+1}$ for all $i$ majorized if $a_{i} > a_{1} + a_{2} + ... + a_{i-1}$ for all $i \ge 2$. Lemma 1. If the problem condition holds with $k \ge 3$, then $S = F \cup B$ where $F$ is a finite set and $B$ is a majorized infinite set. Proof. Suppose for all $n \ge N$, there are exactly $k$ ways to write $n$ in terms of distinct elements of $S$. Let $s_{i}$ be the $i$-th smallest element in $S$. Let $t$ be the smallest integer such that $s_{t} \ge N$. We prove that we can take $B = \{s_{t}, s_{t+1}, s_{t+2}, ...\}$. Consider any $i > j \ge t$. The sum $s_{i} + s_{j}$ can be written in exactly $k$ ways. However, $s_j$ can be written in exactly $k$ ways, so all ways to write $s_{i}+s_{j}$ must contain the element $s_{i}$. On the other hand, consider the $k$ ways to write $s_{i}$. Suppose there is a way to write $s_{i} = s_{i_1} + s_{i_2} + ... + s_{i_p}$ where $i_1 > i_2 > ... > i_p$ with $p \ge 2$ and all indices are not equal to $j$. Then, $s_{i} + s_{j} = s_{j} + s_{i_1} + s_{i_2} + ... + s_{i_p}$ is a way to write $s_{i}+s_{j}$ in terms of distinct elements in $S$ without $s_{i}$, a contradiction. Thus, $s_{j}$ must appear in any sum representation of $s_{i}$ with $\ge 2$ elements for all $t \le j < i$. Hence, $s_{i} = s_{i-1}+s_{i-2}+...+s_{t}+X$ for some $X$. Note that $X>0$ since we require at least two ways to write $X$ in terms of distinct elements in $S$ since $k \ge 3$. Thus, $s_{i} > s_{i-1}+s_{i-2}+...+s_{t}$, proving that $B$ is indeed majorized. For a set of positive integers $T$ and integer $x$, denote $ways(T,x)$ as the number of ways to represent $x$ in terms of distinct elements of $T$. For convenience we let $ways(T,0) = 1$ and $ways(T,x) = 0$ for $x<0$. Lemma 2. Let $B$ be a majorized infinite set. Then, $ways(B, x) \le 1$ for all $x$. Proof. Let $B = \{b_1,b_2,b_3,...\}$ where $b_i<b_{i+1}$ for all $i \ge 1$. Clearly, $ways(B,x) \le 1$ for all $x \le b_1$. Now, we prove the claim $ways(B,x) \le 1$ by strong induction. Suppose $x \ge b_1$. Let $i$ be the largest integer such that $x \ge b_i$. $b_i$ must be included in the sum representation of $x$, since otherwise $b_{i-1}+b_{i-2}+...+b_{1}<b_{i} \le x$. Hence, $ways(B,x) = ways(B,x-b_i) \le 1$ by the induction hypothesis. Let $S = F \cup B$ as in our lemma and let $b_i$ be the $i$-th smallest element of $B$. Consider the infinite binary vector $V = (v_1, v_2, ...)$ where $v_i = ways(B,i)$. Denote $gap(i)$ as $b_{i} - (b_{1}+b_{2}+...+b_{i-1})>0$ since $B$ is majorized. Now, we observe that our vector $V$ takes a special form. Let $V_{1} = (0, 0, ..., 0, 1)$ where there are exactly $b_1$ elements in $V_{1}$. For all $i \ge 2$, we define $V_{i}$ as the vector formed by concatenating $V_{i-1}$, $gap(i)-1$ $0$s, a $1$ followed by another copy of $V_{i-1}$. It can be easily seen similar to lemma $2$ that $V_{i}$ is a prefix of $V$ for all $i \ge 1$ by considering whether we are taking the element $b_i$. Note that $V_{i}$ has $b_1+b_2+...+b_i$ elements and exactly $2^{i} - 1$ $1$s for all $i \ge 1$ (easily proven by induction). Lemma 3. Define $W_{n}$ as the vector obtained by removing the first $n$ elements of $V$. Let $N$ be a fixed positive integer. Then, for any prefix $W$ of $V$, there exists an integer $N' > N$ such that $W$ appears as a prefix of $W_{N'}$. Proof. Let $i$ be the minimum integer such that $V_i$ contains $W$ as a prefix. Then, for all $j \ge i$, $V_j$ contains $W$ as a prefix. Choose $j$ such that the length of $V_j$ is larger than $N$. Note that by the recursive definition, $V_{j+1}$ contains a copy of $V_{j}$ as a substring starting from a position larger than $N$. Thus, we can choose $N'$ appropriately to remove a prefix from $V_{j+1}$ (and thus $V$) such that the starting position is the starting position of the second copy of $V_j$ in $V_{j+1}$. In other words, for any prefix of $V$, we will find that it occurs again as a substring of $V$ infinitely many times. Next, we come to the crucial observation. Lemma 4. For any integer $l$, there exists a prefix of $V$ with length $\ge l$ such that it can be written as the concatenation of $W$, $1$ and $W$ where $W$ is some binary vector containing $2^m - 1$ ones for some $m \ge 0$ (i.e. it is of the form $(w_1, w_2, ..., w_n, 1, w_1, w_2, ..., w_n)$ and exactly $2^m - 1$ of the $w_i$s are $1$s) Proof. Let $N > l^{2020}+2020$. Consider the sequence $gap(N), gap(N+1), gap(N+2), ...$. Since all the terms are positive integers, there must exists some $j \ge N$ such that $gap(j) \le gap(j+1)$. Now, we look at vector $V_{j+1}$. It is the concatenation of $V_{j}$, $gap(j+1)-1$ $0$s, a $1$ followed by $V_{j}$. We focus on the prefix which is the concatenation of $V_{j}$ and $gap(j+1)-1$ $0$s, which can be rewritten as the concatenation of $V_{j-1}$, $gap(j)-1$ $0$s, a $1$, $V_{j-1}$ and $gap(j+1)-1$ $0$s. Since $gap(j) \le gap(j+1)$, choosing $W$ as the concatenation of $V_{j-1}$ and $gap(j)-1$ $0$s work, since $V_{j-1}$ contains exactly $2^{j-1}-1$ $1$s as noted before. Combining Lemma $3$ and Lemma $4$, for any $N$, we can find a substring $V'$ of our vector $V$ of the form $(v_{s}, v_{s+1}, v_{s+2}, ..., v_{s+m-1}, v_{s+m}, v_{s+m+1}, ..., v_{s+2m})$ where $s > N$ and $m \ge sum(F)+2020$ such that $v_{i} = v_{i+m+1}$ for all $s \le i \le s+m-1$, $v_{s+m} = 1$ and any substring of length $m+1$ in $V'$ contains exactly $2^x$ $1$s for some integer $x$ (follows from the fact that the first $m+1$ elements contain exactly $2^x$ $1$s and $v_{i} = v_{i+m+1}$). In particular, choose $N$ such that all integers $\ge N$ can be written as distinct elements of $S$ in exactly $k$ ways. Note that $s+m \ge N$, so $s+m+i$ has exactly $k$ sum representations in $S$ for all $0 \le i \le m$. We will count the total number of sum representations of $s+m$, $s+m+1$, ..., $s+2m$ in $S$ in two ways. Obviously, this sum is equal to $(m+1)k$. On the other hand, let $G = (ways(F,m), ways(F,m-1), ways(F,m-2), ..., ways(F,0))$. Observe that as $m > sum(F)$, the sum of elements in $G$ is exactly $2^{|F|}$. Observe that by fixing the elements to use in $F$, we find that the number of sum representations of $s+m+i$ in $S$ is $\displaystyle\sum_{j=0}^{m}ways(F,m-j)v_{s+i+j}$. Observe that this is equivalent to the dot product of $G$ and a substring of length $m+1$ of $V'$. Summing this value over all $0 \le i \le m$ and using the fact that $V'$ is periodic with period $m+1$, we obtain \[\sum_{i=0}^{m}\sum_{j=0}^{m}ways(F,m-j)v_{s+i+j} = \sum_{j=0}^{m}ways(F,m-j)\sum_{i=0}^{m}v_{s+i+j} = 2^{|F|} \cdot \sum_{i=0}^{m}v_{s+i} = 2^{|F|+x}.\] Hence, $(m+1)k = 2^{|F|+x}$, which means that $k$ divides a power of $2$. Thus, $k$ must be a power of $2$, as desired.

Here is a solution I found during the test. Unfortunately, I got only a few points because I did not write some parts clearly. The answer is all power of $2$ (including 1) First, we will show that all power of 2 work. $$S = \{2^{0}+1,2^{1}+1\hdots,2^{k}+1\}\cup\{1,2,2^2,2^3,\hdots\}.$$clearly satisfies $2^k$. Done. Now, we have to show that the other numbers do not work. $m=1$ are clearly work, so we focus only on $m>1$. Clearly, $S$ much be infinite set. Key claim: For all sufficient large elements $x$ in set $S$, the smallest element larger than $x$ is $2x$. we sprit the proof of the claim into $2$ parts. Part 1: For all sufficient large elements $x$, the smallest integer larger than $x$ in $S$ is greater than or equal to $2x$. In this part, we consider $x>3m$ and assume on a contrary that $a<2x$ is the smallest element larger than $x$. Subcase1 $a\geq\frac{3x}{2}$ In this case, we know that $a$ can be written as a sum of distinct elements of $S$ including $x$ in $m$ ways and $a$ itself is also in $S$. Thus, there are at least $m+1$ ways to write $a$, a contradiction. Subcase2 $a<\frac{3x}{2}$ In this case, we know that $x>2x-a>\frac{x}{2}$.So, $2x$ can be written as a sum of distinct elements of $S$ including $a$ in $m$ ways. But, since $m>1$ so there much be at least one ways to write $x$ ,with each term does not equal to $x$.Hence, we can write $2x$ as a sum of distinct elements of $S$ which does not contain $a$. Thus, there are at least $m+1$ ways to write $a$, a contradiction. Part 2: For all sufficient large elements $x$, the smallest integer larger than $x$ in $S$ is less than or equal to $2x$. From part 1, it suffices to show that $2x$ is a member of $S$. We suppose on a contrary that it is not true. So, $2x$ can be written as a sum of distinct elements containing $x$ in exactly $m-1$ ways. Hence, $2x$ can be written as a sum of distinct elements not containing $x$ in only one way. Suppose if there is any number less than $x-m$ in the sum we can delete them ,it is possible to write some number between $x+m$ and $2x$ not including $x$. However, we know that there is $k$ possible ways to write a number value between $x+m$ and $2x$ including $x$. so there are $k+1$ ways to write it, a contradiction. Otherwise, all elements are larger than $x-m$ which we can check manually that this is impossible. Now our claim is proven. $\blacksquare$ At this point we are ready to finish. From our claim, we can choose $a$ large enough so that we can divide $S$ into 2 disjoint sets $T$ and $\{a,2a,2^{2}a,2^{3}a,\hdots\}$ where $|T|=u$ is finite. Since any integer $n > m$ can be written as a sum of distinct elements of $S$ in exactly $k$ ways. This means the number of subsets $T$ which sum $\equiv t \pmod{a}$ is $\frac{2^u}{a}$ which is a power of 2. From this point, it is clear that only power of $2$ work. $\blacksquare$

The answer is powers of two. For \(k=2^j\), take \[S=\{3,6,9,\ldots,3j\}\sqcup\{1,2,4,8,\ldots\}.\](Here, \(\{3,6,9,\ldots,3j\}\) may be replaced with any set of size \(j\) that does not contain any powers of two.) For sufficiently large \(n\), each subset \(T\) of \(\{3,6,9,\ldots,3j\}\) corresponds to the unique binary representation of \(n-\sum_{t\in T}t\). Now we check only powers of two work. Let \(S=\{s_1<s_2<\cdots\}\), and assume \(k\ge3\). Claim: \(s_1+s_2+\cdots+s_i>s_{i+1}\) for sufficiently large \(i\). Proof. Otherwise \(s_1+s_2+\cdots+s_i\) has at most two representations. \(\blacksquare\) Claim: Let \(m\) be minimal. Then \(s_{i+1}-s_i>m\) for sufficiently large \(i\). Proof. Assume otherwise. Since \(s_1+\cdots+s_{i-1}>s_i\ge s_{i+1}-m\), each representation of \(s_{i+1}-m\) contains an instance of \(s_i\). By removing these \(s_i\)'s there are also exactly \(k\) ways to represent \(m\), contradiction to minimality of \(m\). \(\blacksquare\) Claim: \(s_{i+1}\ge2s_i\) for sufficiently large \(i\). Proof. Otherwise we can find \(k+1\) representations of \(s_{i+1}\): there is \(s_{i+1}\) by itself, and there are also \(k\) representations of \(s_{i+1}-s_i\) with an extra \(s_i\) stuck in. \(\blacksquare\) It is immediate that the sequence \(t_i:=s_1+s_2+\cdots+s_i-s_{i+1}\) is eventually nonnegative and nonincreasing; i.e.\ it is eventually constant. Assume \(t_i=t_{i+1}\) for \(i\ge N\), so for such \(i\) we have \(s_{i+2}=2s_{i+1}\). Then \(s_1\), \ldots, \(s_N\) must generate all residues modulo \(s_{N+1}\) equally often, so \(s_{N+1}\) divides \(2^N\). This means \(S\) has finitely many elements that are not powers of two, so we are done. @below added in some details

@TheUltimate123 Maybe I'm dumb but can you tell me a bit more about why the sequence $t_i$ should be non-increasing?

Part 1. $k=2^r$ works. If $r=0$, then $S=\{1, 2, 4, 8\dots\}$ is a valid set. Now, if $r>0$, we consider $S=\{1, 2, 4, 8, \dots\}\cup A$ where $A$ is a set with $r$ elements which are not powers of two. Let $s_A$ be the sum of the elements of set $A$. Set $m=s_A$. Then for each $n>m$ we can find exactly $2^r=2^{|A|}$ distinct representations of the following kind: we choose one of the $2^{|A|}$ subsets of $A$ and we include these in the sum. When we subtract these from $n$, the resulting number is positive and can be written in a unique way as sum of elements of $\{1, 2, 4, \dots\}$. Part 2. We prove that only powers of two work. Clearly, $S$ is infinite. Let $s_1<s_2<\dots<$ be the elements of $S$. Let $a<b$ be elements of $S$ greater than $m+1$. Adding $a$ to any $n$ with $m+1\le n\le a-1$ will produce $k$ different ways of writing $a+n$ as sum of elements in $S$, since these $n$ cannot contain $a$ in their representations. Since also $b>m+1$, $b$ cannot be in that representation. It follows that the intervals $[m+a+1, 2a-1]$ and $[m+b+1, 2b-1]$ do not intersect because otherwise each integer in its intersection would have both $a$ and $b$ in all its representations. Then $m+b+1\ge (2a-1)+1=2a$, and $b\ge 2a-m-1$. If $a\ge 2(m+1)$, then $b\ge 2a-m-1\ge m+a+1$, and since we cannot have $b\in [m+a+1, 2a-1]$, we even have $b>2a-1$, or $b\ge 2a$. Let $a_1<a_2<\dots<$ be the elements of $S$ greater than $m+1$. Then $a_2\ge 2a_1, a_3\ge 2a_2, \dots$, and in general we have $a_{i+1}-2a_i\ge 0$. The difference $f(i)=s_{i+1}-(s_i+s_{i-1}+s_2+s_2)=s_1+(s_2-2s_1)+(s_3-2s_2)+\dots+(s_{i+1}-2s_i)=f(i-1)+(s_{i+1}-2s_i)$ cannot be greater than $1$, since otherwise $s_{i+1}-1>s_1+s_2+\dots+s_i$ can't be written as sum of elements of $S$. Since eventually $s_{i+1}-2s_i\ge 0$, eventually $f(i)$ is non-decreasing and we must arrive to a moment where $f(i)$ is constant. There is an index $I$ such if $s_{i+1}\ge s_i$ $\forall i\ge I$. Thus we can write $S=A\cup \{b, 2b, 4b, \dots\}$ where $b>\max A$, $b>2(m+1)$. Let $s_A$ be the sum of the elements of $A$. Define $s(i)$ as the sum of ways we can represent the numbers between $1$ and $i$ as sum of elements of $S$. If $i>m$, then we clearly have $s(i)=s(m)+k(i-m)$. Let $t$ be a positive integer such that $2^{t+1}b>s_A$. We calculate $s((2^{t+1}-1)b+s_A)$. On one hand, this is $k\left((2^{t+1}-1)b+s_A-m\right)+s(m)$. Now we do a different calculation. Consider all the representations of numbers as sum of distinct elements of $A\cup\{b, 2b, \dots, 2^tb\}$. This set has $|A|+t+1$ elements. Now, none of these sums is greater than $s_A+b+2b+\dots+2^tb=s_A+(2^{t+1}-1)b$. There are $2^{|A|+t+1}-1$ such ways of choosing non-empty subsets and thus that number of representations. If the representation of a number between $2^{t+1}b$ and $(2^{t+1}-1)b+s_A$ includes $2^{t+1}b$, then the sum of the other numbers is not greater than $(2^{t+1}-1)b+s_A-2^{t+1}b=s_A-b<s_A<2^{t+1}b$. Since $s_A-b<2^{t+1}b$, this can be done in $s(s_A-b)+1$ ways (the $+1$ is because we may not take any element). Finally, none of these representations uses some element of $S$ greater than or equal to $2^{t+2}b$ since \[2^{t+2}b>(2^{t+1}-1)b+s_A \iff\]\[(2^{t+1}+1)b>s_A, \text{ which is true} \]This implies that $s((2^{t+1}-1)b+s_A)=\left[2^{|A|+t+1}-1\right]+\left[s(s_A-b)+1\right]=2^{|A|+t+1}+s(s_A-b)$. Matching with our previous calculation, \[\left((2^{t+1}-1)b+s_A-m\right)k+s(m)=2^{|A|+t+1}+s(s_A-b), \text{ from which}\]\[k=\frac{2^{|A|+t+1}+\left(s(s_A-b)-s(m)\right)}{(2^{t+1}-1)b+s_A-m}. \text{ Analogously,}\]\[k=\frac{2^{|A|+t+2}+\left(s(s_A-b)-s(m)\right)}{(2^{t+2}-1)b+s_A-m}.\]Using the fact that if $a/b=c/d$ then $a/b=c/d=(a-c)/(b-d)$, we obtain \[k=\frac{[2^{|A|+t+2}+\left(s(s_A-b)-s(m)\right)]-[2^{|A|+t+1}+\left(s(s_A-b)-s(m)\right)]}{[(2^{t+2}-1)b+s_A-m]-[(2^{t+1}-1)b+s_A-m]}=\frac{2^{|A|+t+1}}{2^{t+1}b}=\frac{2^{|A|}}{b}.\]Since $k$ is an integer and divides a power of $2$, it must be itself a power of $2$.

TheUltimate123 wrote: Claim: Let \(m\) be minimal. Then \(s_{i+1}-s_i>m\) for sufficiently large \(i\). Proof. Assume otherwise. Since \(s_1+\cdots+s_{i-1}>s_i\ge s_{i+1}-m\), each representation of \(s_{i+1}-m\) contains an instance of \(s_i\). By removing these \(s_i\)'s there are also exactly \(k\) ways to represent \(m\), contradiction to minimality of \(m\). \(\blacksquare\) I didn't understand this proof. If \(s_i\ge s_{i+1}-m\), representations of \(s_{i+1}-m\) can't contain an instance of \(s_i\)!

The answer is all powers of two: $k=2^t$. For the construction, take $S$ to be the powers of $2$ union any $t$ distinct odd positive integers. Now we prove that $k$ must be a power of two. If $k=1$, we are done. Hence assume $k>1$. Let $a_1<a_2<\cdots$ be the elements of $S$ which are greater than $m$. Let $d$ be the sum of integers in the set $S \cap \{1,2,\dots m\}$. Also write $s_i=a_1+a_2+\cdots +a_i$. Call a representation of some number as sum of elements of $S$ 'non-trivial' if at least $2$ elements are used. Claim 1: If $i>j$ then every non-trivial representation of $a_i$ contains $a_j$. Proof: Consider the number $l=a_i+a_j$. If there is some non-trivial representation of $a_i$ not containing $a_j$ then we can get $k+1$ representations of $l$ by using $k$ representations of $a_j$ as well as that one representation of $a_i$ , contradiction. $\blacksquare$ Claim 1 implies that we can write $a_n=b_n+s_{n-1}$ where $b_n$ has exactly $k-1>0$ representations not containing any $a_i$. In particular, this means that $s_{n-1} <a_n $ for all $n>1$. Claim 2: $a_{n+1} \leq 2a_n$ for sufficiently large $n$. Proof: Choose $n$ sufficiently large so that $a_n>d$. Assume FTSOC that $2a_n<a_{n+1}$. Now, $d+s_{n-1}<2a_n$ by our choice of $n$, and since $2a_n \notin S$, every representation of $2a_n$ must contain a term greater than $a_{n-1}$. Since $2a_n<a_{n+1}$ this term must be $a_n$. But that means $2a_n-a_n=a_n$ must have exactly $k$ representations not containing $a_n$, which is a contradiction since there are only $k-1$ such representations. $\blacksquare$ Claim 3: $a_{n+1}=2a_n$ for sufficiently large $n$. Proof: Claim 2 can be rewritten to give $b_{n+1} \leq b_n$ for sufficiently large $n$. Since $b_i$ is bounded below by $0$, it must eventually become constant, which gives us the required claim. $\blacksquare$ Claim 3 implies that sufficiently large elements of $S$ are of the form $a,2a,\dots, 2^ta, \dots$ for some positive integer $a$. Now for the finishing touch we need generating functions: Define $$f(x)= \prod_{s \in S}(1+x^s)$$By the previous discussion we can write $$f(x)=P(x)(1+x^a)\cdots(1+x^{2^ta})\cdots=\frac{P(x)}{1-x^a}$$where $P(x)$ is a polynomial which factorises into products of the form $1+x^l$; in particular, $P(1)$ is a power of $2$. Now, the given condition implies that $f(x)=\frac{k}{1-x}+Q(x)$ for some polynomial $Q$. $$\implies \ \ P(x)=Q(x)(1-x^a)+k(1+x+\cdots+x^{a-1})$$Note that this is now a polynomial relationship, so we can safely put $x=1$ to get $P(1)=ak$. Since $P(1)$ is a power of two, so is $k$, and we are done. $\blacksquare$ Note that the last relation also shows that $a$ must be a power of $2$, so in fact the sufficiently large elements of $S$ must be successive powers of $2$. P.S.: I would really like to see a solution that only uses generating functions (possibly with some analysis) . I recently saw a similar problem by Donald J. Newman which only used GF and some complex analysis.

answer: $k$ should be a power of $2$. Clearly taking $S=\{1,2,2^2,2^3,...\}\cup \{3,3\cdot2,...,3t\} $ works with $k=2^t$ so suppose $k$ is not a power of $2$. Now let $S=\{s_1<s_2<...<s_{m-1}<s_m<...\}$ and suppose that all numbers $n\ge s_m$ have $k$ represantations as sums of elements of $S$. Also denote $A=s_1+...+s_{m-1}$ Every represantation of $s_{m+k}$ contains all of $s_m,s_{m+1},...,s_{m+k-1}$ thus $s_{m+k}>s_m+s_{m+1}+...+s_{m+k-1}$. Elsewise if there is a represantation of $s_{m+k}$ without $s_{m+i}$ then $s_{m+i}+s_{m+k}$ has at least $k+1$ represantations, those of $s_{m+i}$ plus $s_{m+k} $ and the one of $s_{m+k}$ plus $s_{m+i}$. For sufficiently large $n$ say $n\ge m_1$ we have that $s_{n+1}\le 2s_n$ $s_n+s_n $ has $k-1$ represantations containing $s_n$ so we need another one , if it doesen't contain $s_{n+1}$ then we get that $s_1+s_2+...s_{n-1}\ge 2s_n> 2s_m+...+2s_{n-1}$ , $s_1+...s_{m-1}> s_m+...+s_{n-1}$ and say that for $n\ge m_1$ this doesn't hold. We have that $k(s_n+A)\ge 2^{n-1}\ge k(s_n-s_m)$ The former inequality is derived from the fact that every number from $1,...,s_1+s_2+...+s_{n-1}\le s_n+A$ admits at most $k$ represantations as sums of $s_1,...,s_{n-1}$ (that are $2^{n-1}$ in total) and the latter from the fact that $s_m,...,s_n-1$ have $k$ represantations each. For $n\ge m_1$ we have that $2^ps_n\ge s_{n+p}$ so $k2^ps_n+kA\ge 2^{n+p-1}$ for any $p$ which gives that $s_n\ge \frac{2^{n-1}}{k}$ and furthermore $s_n\ge \frac{2^{n-1}}{k}+\frac{1}{k}$ We can show that $s_{n+p}\ge 2^{p-1}(s_m+...+s_n)$ inductively using the previous fact that $s_{n+k+1}\ge s_m+...+s_{n+k}$ then use $2^{n+p-1}\ge ks_{n+p}-ks_m \ge k2^{p-1}(s_m+...s_n)-ks_m$ for any $p$ and finally get that $$\frac{2^n}{k}\ge s_m+....+s_n\ge \frac{2^{m_1-1}}{k}+...+\frac{2^{n-1}}{k}+\frac{n-m_1}{k}$$$$\frac{2^{m_1-1}}{k}\ge \frac{n-m_1}{k}$$for any $n$ which is absurd.

Suppose $N \in S > 3m.$ claim- Next number $x \in S$ after $N$ is $2N.$ If $N<x\le N+m. $ Proof- $N+2m$ can be written in $k$ ways as $N$ and the $k$ ways to make $2m. $ Another $k$ as $x$ and the $k$ ways make $(N+2m-x).$ If $N+m<x<2N. $ Then $x $ can be written as $x$ or as $N. $ $k $ ways make $x-N.$ So $x\ge 2N. $ The sequence of numbers in $S$ can more than double only finitely many times; each time it does, the next number minus the sum of all the previous number shrinks, and if this shrinks to $0.$ Then there is a number we cannot make. Hence, $S$ is of the form $\mathbb F \cup N\{1,2,4,8,16,\hdots \}, $ where $\mathbb F$ is a finite set and $N$ is some natural number.

Answer: $k$ must be the power of 2. Proof: 1. Consider sets $A=\{2^0, 2^1, 2^2, . . . \}$ and $B(t)=\{b_1, . . ., b_t\}$, where $b_1, . . . , b_t$- t different positive integers, none of which lies in the set $A$ ( $B(t)$ is chosen for every nonnegative integer $t$ ). Let's show that any integer $n > b_1+\cdots\ +b_t$ can be written as a sum of distinct elements of $S=A \cup\ B(t)$ in exactly $k=2^t$ ways. Note that any positive integer can be written as the sum of distinct elements of $A$ in exactly one way. So,for any subset $B'$ of $B(t)$ $n$ can be written as the sum of all elements of $B'$ and some elements from $A$ in exactly one away. There are $2^t$ different subsets of $B(t)$, so any integer $n > b_1+\cdots\ +b_t$ can be written as a sum of distinct elements of $S=A \cup\ B(t)$ in exactly $k=2^t$ ways. 2. let's prove that $k$ must be the power of 2. Consider an integer $k$ and a set $S=\{s_1<s_2<s_3<\cdots\}$ of positive integers for which there exist a positive integer $m$ such that any integer $n > m$ can be written as a sum of distinct elements of $S$ in exactly $k$ ways. Claim: $s_{i+1}=2s_i$ for all sufficiently large $i$. Consider the function: $f(i)=s_{i+1}-s_i$. We will look at this function when $i\ge q$, where q is the least number such that $s_q\ge m$. Note that there are 4 possibilities for $f(i)$: a) $f(i)=s_i$, then $s_{i+1}=2s_i$ b) $f(i)=c$ , where $c<s_i$ and $c$ can be represented as a sum of distinct elements of $S$ in exactly $k$ ways. Teh any such representation of $c$ doesn't contain $s_i$. But then the number $s_{i+1}=s_i+c$ can be written as the sum of different integers from $S$ in more than $k$ ways: k ways are obtained by taking some representation of c and adding $s_i$, one more way is representing it as $s_i+1$ itself. Contradiction. c)$f(i)=c$ where $c$ can be represented as a sum of distinct elements of $S$ in less than $k$ ways. Note that then $c\le n\le s_i$ and there is only finite amount of such numbers $c$. d)$f(i)\ge s_i$, than $s_{i+1}\ge 2s_i$. So we see that either $s_{i+1}\ge 2s_i$ for sufficiently large $i$ or there are infinetele many $i$ from c). Let's show that the last situation leads us to contradiction. Assume it's true. C=$\{c_1,c_2,\cdots\}$ - all numbers, satisfying c) which are greater than $q$ ($q$ is the least number such that $s_q\ge m$). From c) it follows that $f(c_i)\le l$ for some $l>0$ and every positive integer $i$. So there are positive integers $u$ and $w$ from $C$ ( $u,w$) such that $f(u)=f(w)=t$. It means that $s_{u+1}=s_u+t$ and $s_{w+1}=s_w+t$, so $s_u+s_{w+1}=s_w+s_{u+1}$. Let's look at the number $s_q+s_u+s_{w+1}$. It is greater than $m$ and at the same time it has more than $k$ different representations as the sum of different elements of $S$: k of them are obtained by taking some representation of $s_q$ (none of them contains $s_u, s_{w+1}, s_w$ or $s_{u+1}$ because $s_q<min(s_u, s_{w+1}, s_w, s_{u+1}$) and adding $s_u+s_{w+1}$ , and other k are obtained by taking some representation of $s_q$ and adding $s_w+s_{u+1}$. Contradiction. So , $s_{i+1}\ge 2s_i$ for sufficiently large $i$. Assume that there are infinetely many $i$ such that $s_{i+1}> 2s_i$ for sufficiently large $i$. Consider the function $g(i)=s_{i+1}-s_i-s_{i-1}-\cdots-s1$. Note that $g(i)<0$ for all sufficiently large $i$ (otherwise \(s_1+s_2+\cdots+s_i\) will have at most two representations). At the same time $g(i)=s_{i+1}-2s_i+g(i)$, so for sufficiently large $i$ $g(i)$ is non-decreasing and for all i $i$, such that $s_{i+1}> 2s_i$ $G(i)\ge 1+g(i-1)$. By our assumption there are infinetely many such $i$ so for sufficiently large $i$ $g(i)>0$. Contradiction. So, for sufficiently large $i$ $s_{i+1}=2s_i$. The claim is proved. Now let $h$ be the least positive integer such that $s_{i+1}=2s_i$ for all $i\ge h$. Note that any number which is the multiple of $s_h$ can be represented as a sum of some different elements from the set $H=\{s_h,s_{h+1}=2s_h, s_{h+2}=2^2*s_h,\cdots\}$ in exactly one way. Any number $f>s_1+s_2+\cdots +s_{h-1}$ can be representated as a sum of different elements from $S$ in exactly $x$ ways, where $x$ is number of subsets of $G$ for which the sum of all their elements and $f$ are the same modulo $s_h$( $G=\{s_1, s_2,\cdots ,s_{h-1}\}$). But by the condition $x=k$ , so for any number $j$ from the set $\{0,1,\cdots , s_h-1 \}$ there are exactly $k$ subsets of $G$ such that the sum of elements of this subset is congruent to $j$ modulo $s_h$. it means that $k$ divides the number of subsets of $G$, so $k$ is the power of 2.

The answer is all $k=2^c$ for some $c\in\mathbb Z_{\geq 0}$ For any set $X$ define $S(X)$ to be the sum of its elements, also $S(\emptyset)=0$. We first show that all these values of $k$ are attainable. CLAIM 1. Suppose $x=2^y$ where $y\in\mathbb N$. There exists a subset $T$ of $\{1,2,...,x-1\}$ such that for all $0\leq i\leq x-1$ there exists exactly $2^y-1$ subset $X$ of $T$ with $$S(X)\equiv i\pmod x$$Proof. We will construct such a subset inductively. If $y=1$ we can just take $T=\{1\}$. Now consider a set $T_y$ for the case $y$, we will define $$T_{y+1}=2T_y\cup\{1,3\}$$where $2S_y=\{2i:i\in S_{y}\}$. It is easy to check that this satisfies the condition. $\blacksquare$ Now it suffices to take $S=T\cup \{2^y,2^{y+1},2^{y+2},...\}$. We pick $m$ such that it is the smallest possible. Now we show that these are the only possibilities. Obviously $S$ is unbounded, let $S=\{a_1,a_2,...\}$. We pick $m$ such that it is the smallest possible. CLAIM 2. Suppose $a_j>a_i>m$ then all decomposition of $a_j$ contains $a_i$. Proof. Consider the number $a_j+a_i$. Notice that there exists subsets $X_1,X_2,...,X_{k-1}\subset\{1,2,...,j-1\}$ such that $$a_j+a_i=a_j+\sum_{x\in X_1}a_x=...=a_j+\sum_{x\in X_{k-1}}a_x$$Therefore, suppose some decomposition of $a_j$ doesn't contain $a_i$, i.e. there exists $Y$ such that $i\notin Y$ and $$a_j=\sum_{x\in Y}a_x$$then $$a_i+\sum_{x\in Y}a_x$$will be the $(k+1)^{th}$ decomposition of $a_j+a_i$, contradiction. $\blacksquare$ Let $T$ be the set of elements in $S$ which is smaller than $m$. Let $S=S(T)$ CLAIM 3. Suppose $c$ is the integer sucht hat $a_{c}\leq S<a_{c+1}$, then for every $c<d$ we have $a_d+m=a_1+a_2+...+a_{d-1}$. Proof. Notice that $m+1$ can be decomposed into elements in $T$, hence $S>m$. Now, there are at most $k-1$ decomposition of $m$, moreover, from CLAIM 2 we have $a_{d+1}>a_d+m$. Therefore, there exists some $X\in\{1,2,...,d-1\}$ such that $$a_d+m=\sum_{x\in X}a_X$$Suppose on the contrary that $X\neq \{1,2,...,d-1\}$. Let $Y=\{1,2,...,d-1\}\setminus X$. We have $$a_d+m+\sum_{Y\in X}a_x=a_1+...+a_{d-1} \hspace{10pt}(1)$$Now there are $k$ decomposition of the number $m+\sum_{Y\in X}a_X$, each of which doesn't contain the number $a_d$ since $a_d\geq a_{c+1}>S$. Therefore, the number in $(1)$ has at least $k+1$ decompositions, contradiction. $\blacksquare$. Now from CLAIM 3 we have $a_i=2a_{i-1}$ for every $i\geq c+1$. CLAIM 4. $ka_{c+1}=2^c$. Proof. Let $U=\{1,2,...,c\}$ and $V=\mathbb N\setminus U$. Notice that every elementn in $a_{c+1}\mathbb N$ can be written uniquely as a sum of distinct elements in $V$. Therefore, for each $1\leq i\leq a_{c+1}$ there exists $k$ subsets $X$ of $U$ such that $$S(X)\equiv i\pmod{a_{c+1}}$$This implies $ka_{c+1}=\text{number of subsets in }U=2^c$ as desired. $\blacksquare$ This obviously implies $k$ is a power of $2$.

shalomrav wrote: TheUltimate123 wrote: Claim: Let \(m\) be minimal. Then \(s_{i+1}-s_i>m\) for sufficiently large \(i\). Proof. Assume otherwise. Since \(s_1+\cdots+s_{i-1}>s_i\ge s_{i+1}-m\), each representation of \(s_{i+1}-m\) contains an instance of \(s_i\). By removing these \(s_i\)'s there are also exactly \(k\) ways to represent \(m\), contradiction to minimality of \(m\). \(\blacksquare\) I didn't understand this proof. If \(s_i\ge s_{i+1}-m\), representations of \(s_{i+1}-m\) can't contain an instance of \(s_i\)! I also think the proof is false.

Solved without Eric Shen, Max Lu, nor Ryan Yang The answer is only $k$ that are powers of $2$. This can be constructed like following: \[S = \{1,2,4,\ldots 2^{k-1}, 2^{k} - 2^{k-2}, \ldots 2^k - 1\} \cup \{ 2^k, 2^{k+1}, \ldots\}\] We show powers of $2$ are the only solutions. Let $S = s_1 < s_2 < \ldots$, and consider taking some $s_i > m + s_1, s_{i-1} > m$. Then, clearly $m+1, \ldots s_{i} - 1$ can be expressed in terms of $s_1, \ldots s_{i-1}$ a total of $k$ times. Now, observe that we can form $s_i +m+1, s_i + m+ 2, \ldots s_i + (s_i -1)$ a total of $k$ times using $s_i$ and the $k$ formations of $m+1, m+2, \ldots (s_i - 1)$. If $s_i+1, s_i+2, \ldots s_i + m$ could not be formed $k$ times, then $s_{i+1} \leq s_i + m$, but then $s_i + s_{i} - 1 \geq s_{i+1} + s_{i-1} \geq s_{i} + m+1$, so some element between $s_{i} + m + 1$ and $2s_{i}-1$ can be formed more than $k$ times, a contradiction. Therefore, every number between $s_i$ and $s_i + m$ can be expressed exactly $k$ times with $s_1, s_2, \ldots s_i$. This means $s_{i+1} \geq 2s_i$. I claim for large enough $i$, we have $s_{i+1} = 2s_i$. This is because, if $s_{i+1} \geq 2s_i$ for large enough $i$, then $s_1 + s_2 + \ldots s_i \leq s_{i+1} + A$ for a constant $A$. Then, if $s_i > A$, we have $2s_i$ can be formed by $s_1, \ldots s_{i-1}$ a total of $0$ times. Then, since $s_i$ can be formed by $s_1, \ldots s_{i-1}$ less than $k$ times, we have $2s_i$ can be formed less than $k$ times by $s_1, \ldots s_i$. We conclude that $s_{i+1} = 2s_i$. Therefore, $s_n = 2^{n-r}c$ for constants $c$ and $r$ and big enough $n$. Consider the numbers formed by $s_1, \ldots s_n$. We can do this in $2^n $ times. For each $m+1, m+2, \ldots 2s_n - 1$, by our above claim, we can construct them exactly $k$ times. Now, I claim the number of ways to construct $2s_i, 2s_i + 1, 2s_i + 2, \ldots$ is a constant $T$. This is because, in a similar vein, since $2s_i = s_{i+1}$, there are exactly $T$ ways to construct $2s_i + s_{i+1}, 2s_i + 1 + s_{i+1}, \ldots$. Furthermore, there are $A$ ways to construct the numbers $1, 2, \ldots m$. Define the constant $R = A + T$, we get: \[2^n = k(2^{n-r}c - m-1) + T\]for all $n$. Then, \[2^{n+1} = k(2^{n+1-r}c - m - 1) + T = k(2^{n-r+1}c - 2(m+1)) + 2T \Rightarrow k(m+1) = T\]\[\Rightarrow 2^{n} = k2^{n-r}c\]Therefore $k$ is a power of $2$, since $c$ is an integer. We conclude that only powers of $2$ work.

Does this solution work? Let $G(x)$ be the generating function for S. Then $G(x)=\prod_{i \in S} (x^i+1)$. By the given conditions, $G(x)=\frac{k}{1-x}+P(x)$, where $P$ is a polynomial. Write $Q(x)=(1-x)P(x)+k$. Then $Q(x) = \frac{\prod_{i \in S} (x^i+1)}{\prod_{j=0} ^{\infty}(x^(2^j)+1)}$. Clearly, $Q(1)=k \neq 0, \infty$. Thus the product of all the polynomial terms in the RHS for the equation for $Q(x)$, evaluated at x=1, must be a power of 2. This forces $k$ to be a power of 2. The rest (construction) can follow like any other solution in this thread. One such construction for $2^x$ is S={1,3,5,7,...,2x+1,2,4,8,16,...}.

@above I think it is a little questionable to say $\frac{2^{\infty}}{2^{\infty}}$ is a power of $2$, as power of 2 is discrete, and when you actually take the limit, all of the terms are not discretely $2$. It could approach really anything. But there is a nice fix with just a quick observation: Suppose $m < x_a, x_{a+1}, \ldots$ then $x_{a+i}$ has $k$ representations. Thus $x_{a+i}+x_{a+j}$ has $k$ representations using $x_{a+i}$, so all representations of $x_{a+j}$ include $x_{a+i}$, and so on. It follows that eventually, by looking at each representation and taking some limit supremums, that we must have $x_{a+i+1} = 2x_{a+i}$ eventually for large $i$. Now we can go back to $k = \lim_{x \to 1} (1-x)\prod_{a \in S}(1+x^a) = k$, which is ill-defined. We can do the replacement $k = \lim_{x \to 1} (1-x) \prod_{a \in S'}(1+x^a) \frac{1}{1-x^s}$ instead, where $s$ is chosen to be minimal where $S*:= \{s, 2s, 4s, \ldots\} \in S$ and $S' = S \setminus S*$. If we take this expression and have it approach a primitive $s$th root of unity, it diverges unless $s = 1$ as none of the $x^a+1$ vanish by the minimality condition, so we must have $s = 1$ since the function is analytical. Thus $k = \lim_{x \to 1} \prod_{a \in S'} (1+x^a) = 2^{|S'|}$, so it must be a power of $2$. Construction is simple.

Let $S$ be written as the sequence $\{x_n\}_{n \ge 1}$ in increasing order. Claim: For sufficiently large $n$, $x_{n+1} \ge 2x_n$. Proof. Assume not. Then, consider the following $k+1$ representations of $x_{n+1}$: the first is $\{x_{n+1}\}$ and the other $k$ are $k$ representations of $x_{n+1}-x_n$ with $x_n$ appended. Now we quote the following: Mickey Mouse during tour of the Atomic Sandwich Splitter wrote: But that's impossible... Claim: For sufficiently large $n$, $x_{n+1} \le 2x_n$. Proof. First, minimize $m$. If $x_{n+1} - x_n \ge m$ for some big $n$, then $x_1+\dots+x_i \ge x_{n+1}-m$, so we have a contradiction since there are thus at least $k$ ways to represent $m$. Thus, $x_{n+1} - x_n < m$ for sufficiently large $n$. By the prior claim, $x_n \ge m$ for sufficiently large $n$, so the claim follows. Lemma: For sufficiently large $n$, $x_{n+1} = 2x_n$. Proof. This is trivial by combining the prior two claims. We proceed with generating functions. Let $F_S$ denote the generating function for the number of ways to write a positive integer as the sum of distinct elements in $S$. Then \[F_S(x) = \prod_{s \in S} (1+x^s). \]By the lemma, we can rewrite this as \[ F_S(x) = \frac{P(x)}{1-x^a} \]for some polynomial $P$ which is the product of factors of the form $(1+x^i)$ and positive integer $a$. Also, \[ F_S(x)=\frac{k}{1- x} + Q(x) \]for some polynomial $Q$. Now we multiply through by $1-x^a$ and compute $P(x)=Q(x)(1-x^a) + k(1+x+\ldots+x^{a-1})$. Legally, we can plug in $x=1$ and find $P(1)=ak$. Since $P(1)$ is also a power of $2$, we now have $k$ a power of $2$, as desired. Remark: This is a very instructive exercise that demonstrates analytic combinatorics, in particular the care required for being able to treat a functional series as a formal series. A more complicated example of this is Shortlist 2015 C6, in which one can, in fact, differentiate the corresponding generating function and use a similar argument involving rearranging to obtain a polynomial equation. The housekeeping is more strict as for the ISL problem.

Solved with GrantStar. The answer is all powers of $2.$ A construction for $k=2^x$ is to take $S=\{1,2,4,\dots\}\cup \{a_1,a_2,\dots,a_x\},$ where no $a_i$ are powers of $2$ since for all $n$ larger than $\sum a_i$ there is one way to write $n-\sum_{i\in T} a_i$ in binary for any subset $T$ of $\{1,2,\dots,x\}.$ Now we show that this is necessary. Consider such a valid set $S,$ which clearly has infinitely many elements. Choose an element $X>2m+2.$ We prove the following: Let $S_{<X}$ be the subset of $S$ containing all of the elements in $S$ that are $<X.$ Then $X$ is the least integer greater than $m$ that cannot be represented as the sum of elements of $S_{<X}$ in $k$ ways. Proof: let $h$ be the least integer as in our claim. If $X<h$ then $X$ can be written as a sum of elements in $S_{<X}$ in $k$ ways, but it can be written in one way as just $X,$ since $X \in S.$ Thus $X$ can be written in total as at least $k+1$ ways, impossible. If $X>h$ then all elements of $S$ that are part of sums that equal $h$ are also in $S_{<X},$ and so, $h$ can be written as the sum of elements in $S$ in less than $k$ ways, impossible. Thus the claim is proved. Next, let $Y$ be the smallest element of $S$ greater than $X.$ We show that $Y\ge 2X.$ To do this, first if $X<Y\le X+m$ then $X+2m+1$ can be represented in $k$ ways as the sum of $X$ and elements in $S_{<X}$ but can also be represented in $k$ ways as the sum of $Y$ and elements in $S_{<X},$ since $X+2m+1-Y\ge X+2m+1-(X+m)>m$ and $X+2m+1-Y<X+2m+1-X=2m+1<X.$ Next if $X+m<Y<2X$ then $m<Y-X<X$ so $Y$ can be written as the sum of $X$ and elements in $S_{<X}$ in $k$ ways, as well as just $Y$ in one way, giving a total of at least $k+1$ ways, also impossible. Now, let $\sigma_X$ be the sum of all elements in $S_{<X}.$ Similarly, let $\sigma_Y$ be the sum of all elements in $S_{<Y}=X\cup S_{<X}.$ We see that $\sigma_Y-2Y=\sigma_X+X-2Y<\sigma_X-Y\le \sigma_X-2X.$ Thus, by adding on the next smallest element of $S,$ we can make $\sigma_X-2X$ decrease. We can repeat this until we have some $Z$ such that $\sigma_Z-2Z$ is negative. Then $\sigma_{Z'}-2Z'$ is negative as well for all $Z'\in S,Z'>Z.$ Thus, for all elements $A$ of $S$ greater than $Z,$ we consider the smallest element $B$ that is larger than $A.$ As above we have shown that $B \ge 2A.$ Letting $S_{<A}$ be the subset of $S$ containing all elements $<A,$ we have by our first claim that $A$ cannot be represented in $k$ ways using only elements of $S_{<A}.$ As we have just showed, we also cannot represent $2A$ using only elements of $S_{<A},$ as it is too big. Thus $2A$ can be represented by elements of $A\cup S_{<A}$ in $<k$ ways, and as such, by our claim we have $B=2A.$ Thus all sufficiently large elements of $S$ are twice the next smallest element. Now, let $P$ be the smallest element of $S$ such that all elements of $S$ greater than $P$ are of the form $2^iP.$ Let $p$ be a prime dividing $P,$ and let $Q$ be the set of elements of $S$ not divisible by $p.$ Since all large enough integers will have the same number of representations, all residue classes $\pmod p$ will approach having equal numbers of representations. Thus, each residue class has the same number of ways to be represented by the sum of a subset of $Q.$ This then implies that $p \mid 2^{|Q|},$ so $p=2$ and thus all large enough elements of $S$ are powers of $2.$ Finally, to show that $k$ is a power of $2,$ consider $P$ again. Let $S_{<P}$ be the set of elements of $S$ smaller than $P.$ Consider the integers $hP+1,hP+2,\dots,hP+P$ for an arbitrarily large integer $h.$ Each of these must have $k$ representations. Consider $hP+1-\sum_{a \in J}a,hP+2-\sum_{a \in J} a,\dots,hP+P-\sum_{a\in J}a,$ for any subset $J$ of $S_{<P}.$ Exactly one of these are divisible by $P,$ and we can see that if a large enough integer is not divisible by $P,$ it cannot be represented by elements of $S\backslash S_{<P},$ and if it is divisible by $P,$ it can be represented in exactly one way, by its binary representation multiplied by $P.$ Thus these $P$ integers together have exactly one representation by elements of $S\backslash S_{<P}.$ However, notice that when summing this across all $J,$ we are counting the total number of representations of $hP+1,hP+2,\dots,hP+P.$ Then this total is $2^{|S_{<P}|},$ and the number of representations of each of these is then $k=\frac{2^{|S_{<P}|}}P,$ which is a power of $2.$

The answer is $2^t$ for nonnegative integers $t$, achievable by taking $S$ to be all powers of $2$ along with $t$ extra numbers. We now show $k$ must be a power of $2$. Write the elements of $S$ as an increasing sequence $a_1 < a_2 < \dots$, and let $a_x$ be the first element greater than $m$. Claim: If $a_i\ge 2a_x$ then $a_{i+1}\ge 2a_i$. Proof: Suppose otherwise. We will consider two cases. If $a_{i+1}\ge a_i+m$, then $a_{i+1}-a_i$ is between $m$ and $a_i$. Hence, $a_{i+1}$ can be written as a sum of elements of $S$ including $a_i$ in exactly $k$ ways, a contradiction since it can also be written as just $a_{i+1}$. If $a_{i+1}<a_i+m$, then $a_{i+1}+a_x-a_i$ is between $m$ and $a_i$. Hence, $a_{i+1}+a_x$ can be written as a sum of elements of $S$ including $a_i$ in exactly $k$ ways, a contradiction since it can also be written as just $a_{i+1}+a_x$. The claim is proved. Claim: There exists an index $y$ such that $a_{i+1} = 2a_i$ for all $i\ge y$. Proof: Suppose otherwise. Then $a_{i+1}\ge 2a_i+1$ for infinitely many $i$. Consider the prefix sums $s_i = a_1+a_2+\dots+a_i$. Note that $s_i-a_{i+1}=s_{i-1}+a_i-a_{i+1}=(s_{i-1}-a_i)-(a_{i+1}-2a_i)$. Hence, the sequence $s_i-a_{i+1}$ is eventually non-increasing and decreases infinitely many times. But if $s_i<a_{i+1}$ for any $i$ then $a_{i+1}$ can only be written as a sum of elements of $S$ in only $1$ way, absurd. The claim is proved. To finish, pick a number $N>>s_y$. Note that for each $r=0,\dots,a_y-1$, the number of ways to write $N\cdot a_y+r$ as a sum of distinct elements of $S$ is precisely the number of subsets of $\{a_1,\dots,a_{y-1}\}$ with sum equivalent to $r\pmod{a_y}$. Since each subset is counted exactly once, it follows that $s_y\cdot k = 2^{y-1}$, implying $k$ is a power of $2$, as desired.