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.

Step 5 of 5: Count representations by residue to force k a power of two

Previous step Next step

\#\{T'\subseteq T: s(T')\equiv y \pmod x\}=k\ \text{ for every residue},\quad kx=2^{|T|}

Detailed analysis

Since any nonnegative integer has a unique representation as a sum of distinct elements of $\{x,2x,4x,\ldots\}$ once it is a large enough multiple of $x$ , the number of ways to write a large $y$ as a sum of distinct elements of $S$ equals the number of subsets $T'\subseteq T$ with $s(T')\equiv y\pmod x$ . This count must equal $k$ for every one of the $x$ residue classes, so $kx$ equals the total number of subsets of $T$ , namely $2^{|T|}$ . Hence $k$ divides $2^{|T|}$ , so $k$ is a power of two, completing the classification.