Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2013 USAJMO Problems/Problem 4"
m (Original prove is wrong)
Line 4: Line 4:
 
==Solution==
 
==Solution==
  
−
First of all, note that <math>f(n)</math> = <math>\sum_{i=1}^{k} f(n-2^{i})</math> where <math>k</math> is the largest integer such that <math>2^k \le n</math>.  We let <math>f(0) = 1</math> for convenience.   
+
First of all, note that <math>f(n)</math> = <math>\sum_{i=0}^{k} f(n-2^{i})</math> where <math>k</math> is the largest integer such that <math>2^k \le n</math>.  We let <math>f(0) = 1</math> for convenience.   
  
 
From here, we proceed by induction, with our claim being that the only <math>n</math> such that <math>f(n)</math> is odd are <math>n</math> representable of the form <math>2^{a} - 1, a \in \mathbb{Z}</math>
 
From here, we proceed by induction, with our claim being that the only <math>n</math> such that <math>f(n)</math> is odd are <math>n</math> representable of the form <math>2^{a} - 1, a \in \mathbb{Z}</math>

Revision as of 23:15, 24 September 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=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=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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2013_USAJMO_Problems/Problem_4&oldid=57153"