2013 USAJMO Problems/Problem 4

Problem

Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$ , where we keep track of the order of the summation. For example, $f(4)=6$ because $4$ can be written as $4$ , $2+2$ , $2+1+1$ , $1+2+1$ , $1+1+2$ , and $1+1+1+1$ . Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.

Solution

First of all, note that $f(n)$ = $\sum_{i=0}^{k} f(n-2^{i})$ where $k$ is the largest integer such that $2^k \le n$ . We let $f(0) = 1$ for convenience.

From here, we proceed by induction, with our claim being that the only $n$ such that $f(n)$ is odd are $n$ representable of the form $2^{a} - 1, a \in \mathbb{Z}$

We induct on $a$ . It is trivially true for $a = 0$ and $a = 1$ . From here, we show that, if the only numbers $n \le 2^{a-1} - 1$ where $f(n)$ is odd are of the form described above, then the only numbers $n \le 2^{a} -1$ that are odd are of that form. We first consider all numbers $b$ , such that $2^{a-1} \le b \le 2^{a} - 2$ , going from the lower bound to the upper bound (a mini induction, you might say). We know that $f(b) = \sum_{i=0}^{a-1} f(b-2^{i})$ . For a number in this summation to be odd, $b - 2^i = 2^m -1 \rightarrow b = 2^i + 2^m - 1$ . However, we know that $b > 2^{a-1}$ , so $m$ must be equal to $a-1$ , or else $b$ cannot be in that interval. Now, from this, we know that $i < a-1$ , as $b<2^{a} - 1$ . Therefore, $i$ and $m$ are distinct, and thus $f(b - 2^i)$ and $f(b- 2^{a-1})$ are odd; since there are just two odd numbers, the ending sum for any $b$ is even. Finally, considering $2^{a} - 1$ , the only odd number is $f(2^{a} - 1 - 2^{a-1})$ , so the ending sum is odd. $\Box$

The smallest $n$ greater than $2013$ expressible as $2^d - 1, d \in \mathbb{N}$ is $2^{11} -1 = \boxed{2047}$

Solution with Explanations

Of course, as with any number theory problem, use actual numbers to start, not variables! By plotting out the first few sums (do it!) and looking for patterns, we observe that $f(n)=\sum_{\textrm{power}=0}^{\textrm{pow}_{\textrm{larg}}} f(n-2^{\textrm{power}})$ , where $\textrm{pow}_{\textrm{larg}}$ represents the largest power of $2$ that is smaller than $n$ . I will call this sum the Divine Sign, or DS.

But wait a minute... we are trying to determine odd/even of $f(n)$ . Why not call all the evens 0 and odds 1, basically using mod 2? Sounds so simple. Draw a small table for the values: as $n$ goes up from $0$ , you get: $1,1,0,1,0,0,0,1,0...$ . We have to set $f(0)=1$ for this to work. Already it looks like $f(n)$ is only odd if $n=2^{\textrm{power}}-1$ .

The only tool here is induction. The base case is clearly established. Then let's assume we successfully made our claim up to $2^n-1$ . We need to visit numbers from $2^n$ to $2^{n+1}-1$ . Realize that $2^n$ has $0$ for $f$ because there will be two numbers in DS that give a $f$ of one: $2^{n-1}$ and $1$ .

But to look at whether a value of $f(\textrm{number})$ is 1 or 0, we need to revisit our first equation. We can answer this rather natural question: When will a number to be inducted upon, say $2^n+k$ , ever have a 1 as $f(\textrm{number})$ in the DS equation? Well- because by our assumption of the claim up to $2^n-1$ , we know that the only way for that to happen is if $2^n+k-2^{\textrm{power}}$ in the DS is equal to $2^{\textrm{Some power}} - 1$ . Clearly $1 \leq k \leq 2^n - 1$ .

Finally, we can simplify. Using our last equation, $2^n+k-2^{\textrm{power}}=2^{\textrm{Some power}}-1$ , regrouping gives $2^n+k=2^{\textrm{power}}+2^{\textrm{Some power}}-1$ .

Most importantly, realize that $\textrm{power}$ can be from $0$ to $n$ , because of the restraints on $k$ mentioned earlier. Same with $\textrm{Some power}$ . Immediately at least one of $\textrm{power}$ and $\textrm{Some power}$ has to be $n$ . If both were smaller, LHS is greater, contradiction. If both were greater, RHS is greater, contradiction.

Therefore, by setting one of $\textrm{power}$ or $\textrm{Some power}$ to $n$ , we realize $k=2^{\textrm{A certain power}}-1$ .

The conclusion is clear, right? Each $k$ from $1$ to $2^{n-1}-1$ yields two distinct cases: one of $\textrm{power}$ and $\textrm{Some power}$ is equal to $n$ , while the other is LESS THAN $n$ . But for $k=2^n-1$ , there is ONE CASE: BOTH values have to equal $n$ . Therefore, the only $k$ that has $f(2^n+k)$ as odd must only be $2^n-1$ , because the other ones yield a $f$ of 1+1=0 in our mod. That proves our induction for a new power of 2, namely $n+1$ , meaning that $f(\textrm{number})$ is only odd if $\textrm{number} = 2^{\textrm{Power of two}} - 1$ , and we are almost done...