Putnam 2003, Problem A-6

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 \neq 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 \)?

Solution:
### First solution:  
Yes, such a partition is possible. To achieve it, place each integer into \( A \) if it has an even number of 1s in its binary representation, and into \( B \) if it has an odd number. (One discovers this by simply attempting to place the first few numbers by hand and noticing the resulting pattern.)  

To show that \( r_A(n) = r_B(n) \), we exhibit a bijection between the pairs \( (a_1,a_2) \) of distinct elements of \( A \) with \( a_1 + a_2 = n \) and the pairs \( (b_1,b_2) \) of distinct elements of \( B \) with \( b_1 + b_2 = n \). Namely, given a pair \( (a_1,a_2) \) with \( a_1 + a_2 = n \), write both numbers in binary and find the lowest-order place in which they differ (such a place exists because \( a_1 \neq a_2 \)). Change both numbers in that place and call the resulting numbers \( b_1,b_2 \). Then \( a_1 + a_2 = b_1 + b_2 = n \), but the parity of the number of 1s in \( b_1 \) is opposite that of \( a_1 \), and likewise between \( b_2 \) and \( a_2 \). This yields the desired bijection.  


### Second solution: (by Micah Smukler)  
Write \( b(n) \) for the number of 1s in the base 2 expansion of \( n \), and \( f(n) = (-1)^{b(n)} \). Then the desired partition can be described as \( A = f^{-1}(1) \) and \( B = f^{-1}(-1) \). Since \( f(2n) + f(2n + 1) = 0 \), we have  
\[
\sum_{i=0}^n f(i) = \begin{cases} 
0 & \text{if } n \text{ odd}, \\
f(n) & \text{if } n \text{ even}.
\end{cases}
\]  
If \( p, q \) are both in \( A \), then \( f(p) + f(q) = 2 \); if \( p, q \) are both in \( B \), then \( f(p) + f(q) = -2 \); if \( p, q \) are in different sets, then \( f(p) + f(q) = 0 \). In other words,  
\[
2(r_A(n) - r_B(n)) = \sum_{p+q=n, p<q} (f(p) + f(q))
\]  
and it suffices to show that the sum on the right is always zero. If \( n \) is odd, that sum is visibly \( \sum_{i=0}^n f(i) = 0 \). If \( n \) is even, the sum equals  
\[
\left( \sum_{i=0}^n f(i) \right) - f(n/2) = f(n) - f(n/2) = 0.
\]  
This yields the desired result.  


### Third solution: (by Dan Bernstein)  
Put \( f(x) = \sum_{n \in A} x^n \) and \( g(x) = \sum_{n \in B} x^n \); then the value of \( r_A(n) \) (resp. \( r_B(n) \)) is the coefficient of \( x^n \) in \( f(x)^2 - f(x^2) \) (resp. \( g(x)^2 - g(x^2) - g(x^2) \)). From the evident identities  
\[
\frac{1}{1 - x} = f(x) + g(x), \quad f(x) = f(x^2) + xg(x^2), \quad g(x) = g(x^2) + xf(x^2),
\]  
we have  
\[
f(x) - g(x) = f(x^2) - g(x^2) + xg(x^2) - xf(x^2) = (1 - x)(f(x^2) - g(x^2)) = \frac{f(x^2) - g(x^2)}{f(x) + g(x)}.
\]  
We deduce that \( f(x)^2 - g(x)^2 = f(x^2) - g(x^2) \), yielding the desired equality.  

**Note:** This partition is actually unique, up to interchanging \( A \) and \( B \). More precisely, the condition that \( 0 \in A \) and \( r_A(n) = r_B(n) \) for \( n = 1, \ldots, m \) uniquely determines the positions of \( 0, \ldots, m \). We see this by induction on \( m \): given the result for \( m - 1 \), switching the location of \( m \) changes \( r_A(m) \) by one and does not change \( r_B(m) \), so it is not possible for both positions to work. Robin Chapman points out that this problem is solved in D.J. Newman’s *Analytic Number Theory* (Springer, 1998); in that solution, one uses generating functions to find the partition and establish its uniqueness, not just verify it.