Not That Hard I Guess
Algebra
Level
1
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 for each n?
No
Yes
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The answer is : Yes.
Here's how you do this :
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 if 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.