Is it possible to partition {0, 1, 2, 3, ... } into two parts such that n = x + y with x ≠ y has the same number of solutions in each part?
Answer
Yes.
Solution
Put A = numbers with an odd number of binary digits, B = numbers with an even number of binary digits. Let S be the set of pairs (a,b) with a ≠ b and a, b non-negative. Define f: S → S as follows. Given (a,b) ∈ S take the first digit from the right which differs in a and b and switch it in both to give (a',b'). Evidently (a',b') ∈ S and a + b = a' + b'. Also f is its own inverse. Note that (a,b) is a pair of numbers from A iff f(a,b) is a pair of numbers from B. Thus f gives a bijection between solutions of n = x + y in A and solutions in B.
© John Scholes
jscholes@kalva.demon.co.uk
8 Dec 2003
Last corrected/updated 8 Dec 03