APMO 2020 Problem 3

Determine all positive integers $k$ for which there exist a positive integer $m$ and a set $S$ of positive integers such that any integer $n > m$ can be written as a sum of distinct elements of $S$ in exactly $k$ ways.

I was totally screwed by a mistake and thought $k=1$. My excuse is that I didn't have a chance to sit down and think about it seriously. So below are just my proof after knowing that $k$ can only be power of two.



We say a number is good if it could be written as the sum of distinct elements of $S$ in exactly $k$ ways.

Let $s_1 \lt s_2 \lt \ldots \lt \ldots$ denote the good numbers in $S$. Let $S_1 \lt S_2 \lt \ldots \lt \ldots$ constitute $S$.

Lemma 1
There does not exist number $x+S_j=S_i+S_k\gt m$ where $x\lt S_j$, $x\notin\{S_i,S_k\}$, and $x$ is good.
Proof
If it does, then $x+S_j$ has at least $k+1$ representations, a contradiction.
$\square$

Lemma 2
For sufficiently large $i$, $2s_i\leq s_{i+1}$.
Proof
If not, let $x=s_{i+1}-s_i \lt s_i$. If $x \gt m$ then $x$ is good and $s_{i+1}$ has at least $k+1$ representations, a contradiction. If $x\leq m$, then given $s_i$ is sufficiently large we can find $S_a \lt y \lt s_i \lt s_{i+1}$ such that $y$ is good and $y+s_i=S_a+s_{i+1}$ which contradicts Lemma 1.
$\square$

With this, let $a=s_i\gt m$ where $2s_j\leq s_{j+1}$ for any $j\ge i$. Let $S'=\{x: x\lt a, x\in S\}$ and $t$ be the sum of elements in $S'$.

Lemma 3 
$t\leq a+m$
Proof
Note that $a+m$ is less than the next element in $S$ after $a$. If $a+m\lt t$, then $t$ has at least $k+1$ representations where $k$ of them come from representations of $t-a$ and an extra from $S'$, a contradiction.
$\square$

Lemma 4
$k$ is a power of two.
Proof
Double count representations using only $S'$. Define $f(n)$ as the number of representations using $S$. For $x\in[0, a-1]$, $f(x)$ completely comes from $S'$. For $x\in[a, a+m]$, $f(x)-f(x-a)$ counts representations using only $S'$. So the quantity

$$
f(0)+f(1)+\ldots+f(a-1)+\left(f(a)-f(0)\right)+\left(f(a+1)-f(1)\right)+\ldots+\left(f(a+m)-f(m)\right),
$$

reduced to $f(m+1)+\ldots+f(a+m)=ak$, is equal to $2^{|S'|}$, therefore $k$ must be a power of two.

$\square$

Finally, for any $k=2^{k'}$, the desired $S$ could be $S=\{3^0,3^1,\ldots,3^{k'}\}\cup\{2^0,2^1,\ldots\}$.