Does there exist a subset S of the integers such that, given any integer n, the equation n = 2s + s' has exactly one solution in S? For example, if T = {-3, 0, 1, 4), then there are unique solutions -3 = 2·0 - 3, -1 = 2·1 - 3, 0 = 2·0 + 0, 1 = 2·0 + 1, 2 = 0 + 2·1, 3 = 2·1 + 1, 4 = 2·0 + 4, 5 = 2·-3 + 1, but not for 6 = 2·1 + 4 = 2·-3 + 0, so T cannot be a subset of S.
Solution
Answer: yes.
We show how to choose S inductively. Suppose we have already chosen a1, a2, ... , an, but we do not yet have a solution for m ≥ 0. Take N so that all |ai| < N. Now take an+1 = 5N + m, an+2 = -10N - m. This gives a solution for m: m = 2an+1 + an+2, but it does not duplicate any existing solutions, since |2an+2 + an+1|, |2an+1 + ai|, |2an+2 + ai|, |an+1 + 2ai|, |an+2 + 2ai| are all ≥ 3N, whereas all existing sums have absolute value < 3N. Similarly for m < 0, we may take an+1 = - 5N + m, an+2 = 10N - m.
Comment. The problem (and the opportunity) is that since positive and negative numbers are allowed |s| and |s'| can be arbitrarily large and still give n = 2s + s'. Compare the similar problem where S must be a subset of the non-negative integers and we require a unique solution n = 2s + s' for all non-negative n. In this case we can give S explicitly as all numbers with just the digits 0 and 1 in base 4. In fact, the same idea works for the case of all the integers, but it requires a little more work to show that -4 works as a number base.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002