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_{1}^{k} f(n-2^{k})$ 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}$

Page

Toolbox

Search

2013 USAJMO Problems/Problem 4

Problem

Solution