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 2 of 5: Construction for k=2^a

Previous step Next step

A=\{1,2,4,8,\ldots\},\quad S=A\cup B',\ |B'|=a,\ B'\subseteq\mathbb{N}\setminus A

Detailed analysis

Let $A$ be the powers of two and let $B'$ be any set of $a$ positive integers not in $A$ . Put $S=A\cup B'$ . Every nonnegative integer has a unique representation as a sum of distinct powers of two, so for $t$ larger than the sum of $B'$ and any subset $B''\subseteq B'$ , the number $t-s(B'')$ has a unique representation using $A$ ; letting $B''$ range over the $2^a$ subsets of $B'$ shows $t$ has exactly $2^a$ representations as a sum of distinct elements of $S$ .