Putnam 2003 A6

For a set $S$ of nonnegative integers, let $r_S(n)$ denote the number of ordered pairs $(s_1,s_2)$ such that $s_1 \in S$, $s_2 \in S$, $s_1 \ne s_2$, and $s_1+s_2 = n$. Is it possible to partition the nonnegative integers into two sets $A$ and $B$ in such a way that $r_A(n) = r_B(n)$ for all $n$?

Well, let's try to start doing it and see what we can come up with. So let's put $0$ in $A$, and then we'll have to put $1$ in $B$ because otherwise $r_A(1)$ will be $2$ and $r_B(1)$ will be $0$. Similarly, we have to put $2$ in $B$ because otherwise $r_A(2)$ will be $2$ and $r_B(2)$ will be $0$. And $3$ goes in $A$ because $r_B(3) = 2$ so we need $r_A(3) = 2$. If we keep going like this for awhile, we get \[ A = \{ 0, 3, 5, 6, 9, 10, 12, 15, \ldots \}, \, \, B = \{ 1, 2, 4, 7, 8, 11, 13, 14, 16, \ldots \} \] You can find a decent number of patterns when you write this out--it's a good exercise to do it yourself--but it looks like we can keep going forever. So we'll have to try to find an intrinsic description of the sets and prove that the sets with those descriptions have the property we want.

Well, I guess the best way to hit on the right answer is to notice that there are patterns that (sort of) recur every 2, 4, 8, 16... numbers. That might make us think of binary expansions. If we write the numbers in $A$ and $B$ in binary, we see the pattern: $A$ is the set of numbers with an even number of $1$s in their binary expansions, $B$ is the set of numbers with an odd number of $1$s in their binary expansions.

So let's see why $r_A(n) = r_B(n)$ for every $n$. Maybe it would be easiest to do an example: e.g. $r_A(15) = 8$ because of $0+15, 3+12, 5+10, 6+9$. And $r_B(15) = 8$ because of $1+14, 2+13, 4+11, 7+8$. You can see that we can get from each of the sums in $A$ to a sum in $B$ by adding and subtracting $1$, respectively, from the numbers. Though that doesn't always work...look at $r_A(6) = 2$ ($0+6$) and $r_B(6) = 2$ ($2+4$). But there is still that adding and subtracting the same number. Hmm.

So the right idea is to start with a sum of two things in $A$, and convert it to a sum of two things in $B$. Here's a thought: take the rightmost binary digit where the numbers in $A$ disagree (e.g. with $000$ and $110$, it's the twos digit--note that this is where we use the $s_1 \ne s_2$ hypothesis). Then one of them is a $0$ and one of them is a $1$. Try the effect of switching the $0$ and $1$ (e.g. getting $010$ and $100$ in our example). Note that the sum is the same, and the number of $1$s in the binary expansions of the numbers changes by $1$--either from even to odd or vice versa.

So this process illustrates a one-to-one correspondence between the pairs in $A$ and the pairs in $B$. Hence the answer is ``yes" and we are done.

Top 201 scores:
(18,6,4),(7,4,162)