Determine all positive integers for which there exist a positive integer and a set of positive integers such that any integer can be written as a sum of distinct elements of in exactly ways.
Solutions — 2
Solution 1
We claim that for all .
Let and . For any set , let denote the sum of the elements of . (If is empty, we let .)
We first show that any positive integer satisfies the desired property. Let be a subset of with elements, and let . Recall that any nonnegative integer has a unique binary representation. Hence, for any integer and any subset , the number can be written as a sum of distinct elements of in a unique way. This means that can be written as a sum of distinct elements of in exactly ways.
Next, assume that some positive integer satisfies the desired property for a positive integer and a set . Clearly, is infinite.
Lemma: For all sufficiently large , the smallest element of larger than is .
Proof of Lemma: Let with , and let . We will show that . Suppose first that . Then can be written as a sum of distinct elements of not including in ways. If , then can be written as a sum of distinct elements of in at least ways, a contradiction. Suppose now that . We consider . Similarly as before, can be written as a sum of distinct elements of not including or in ways. If , then since , can be written as a sum of distinct elements of not including or . This means that can be written as a sum of distinct elements of in at least ways, a contradiction.
We now show that ; assume for contradiction that this is not the case. Observe that can be written as a sum of distinct elements of including in exactly ways. This means that can also be written as a sum of distinct elements of not including . If this sum includes any number less than , then removing this number, we can write some number as a sum of distinct elements of not including . Now if where then can be written as a sum of distinct elements of including in exactly ways. Therefore can be written as a sum of distinct elements of in at least ways, a contradiction. Hence the sum only includes numbers in the range . Clearly two numbers do not suffice. On the other hand, three such numbers sum to at least , a contradiction.
From the Lemma, we have that , where is finite and for some positive integer . Let be any positive integer greater than . For any subset , if , then can be written as a sum of distinct elements of in a unique way; otherwise cannot be written as a sum of distinct elements of . Hence the number of ways to write as a sum of distinct elements of is equal to the number of subsets such that . Since this holds for all , for any there are exactly subsets such that . This means that there are subsets of in total. But the number of subsets of is a power of , and therefore is a power of , as claimed.
Solution 2
Solution 2. We give an alternative proof of the first half of the lemma in the Solution 1 above.
Let be the elements of . For any positive integer , define . For each such that , all ways of writing as a sum of elements of must only use , so the coefficient of in is . Similarly the number of ways of writing as a sum of elements of without using is exactly . Hence the coefficient of in is .
Fix a such that . Write
for some where is of degree at most .
Note that
If , we can find the term in and in . Hence the coefficient of in is at least , which is impossible. So .
Now
Recall that the coefficent of in is . But if , then the coefficient of in is at least , which is a contradiction. Therefore .