Difference between revisions of "2013 USAJMO Problems/Problem 4"

Line 11: Line 11:
  
 
The smallest <math>n</math> greater than <math>2013</math> expressible as <math>2^d - 1, d \in \mathbb{N}</math> is <math>2^{11} -1 = \boxed{2047}</math>
 
The smallest <math>n</math> greater than <math>2013</math> expressible as <math>2^d - 1, d \in \mathbb{N}</math> is <math>2^{11} -1 = \boxed{2047}</math>
 +
{{MAA Notice}}

Revision as of 17:02, 3 July 2013

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=1}^{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=1}^{a-1} f(n-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 $n$ cannot be in that interval. Now, from this, we know that $i < a-1$, as $n<2^{a} - 1$. Therefore, $i$ and $m$ are distinct, and thus $f(n - 2^i)$ and $f(n- 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}$ The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png