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

Revision as of 23:20, 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=0}^{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=57154"