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 3 of 5: Lemma: consecutive large elements of S double

Previous step Next step

x\in S,\ x<y<2x \implies y\notin S,\quad 2x\in S

Detailed analysis

Assume the data work. The set S is infinite, since a finite set has only finitely many subset sums. Take a sufficiently large element x of S. If another element y of S lay strictly between x and twice x, first consider y more than x plus m: the k representations of y minus x avoid x, and adjoining x gives k representations of y in addition to its one-element representation. If y is at most x plus m, then for m at least 2 choose an integer z strictly between twice x minus m and twice x; for m=1 use z=twice x and use the k−1 representations of x other than its one-element representation. In either case, adjoining x and y to representations of z minus x and z minus y gives more than k representations of z. Thus no such y exists. If twice x were not in S, the k representations of twice x using x would be exactly all but one of the representations of x. The remaining representation avoids x; deleting a term below x minus m would produce a forbidden element between x and twice x, while using only terms from x minus m up to x cannot sum to twice x with either two or three terms. Hence twice x belongs to S.