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"
(Added new solution.)
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>
 +
 +
==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 <math>f(n)=\sum_{power=0}^{pow_{larg}} f(n-2^{power})</math>, where <math>pow_{larg}</math> represents the largest power of <math>2</math> that is smaller than <math>n</math>. I will call this sum the Divine Sign, or DS.
 +
 +
But wait a minute... we are trying to determine odd/even of <math>f(n)</math>. 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 <math>n</math> goes up from <math>0</math>, you get: <math>1,1,0,1,0,0,0,1,0...</math>. We have to set <math>f(0)=1</math> for this to work. Already it looks like <math>f(n)</math> is only odd if <math>n=2^{power}-1</math>.
 +
 +
The only tool here is induction. The base case is clearly established. Then let's assume we successfully made our claim up to <math>2^n-1</math>. We need to visit numbers from <math>2^n</math> to <math>2^{n+1}-1</math>. Realize that <math>2^n</math> has <math>0</math> for <math>f</math> because there will be two numbers in DS that give a <math>f</math> of one: <math>2^{n-1}</math> and <math>1</math>.
 +
 +
But to look at whether a value of <math>f(number)</math> 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 <math>2^n+k</math>, ever have a 1 as <math>f(number)</math> in the DS equation? Well- because by our assumption of the claim up to <math>2^n-1</math>, we know that the only way for that to happen is if <math>2^n+k-2^{power}</math> in the DS is equal to <math>2^{somePower} - 1</math>. Clearly <math>1 \leq k \leq 2^n - 1</math>.
 +
 +
Finally, we can simplify. Using our last equation, <math>2^n+k-2^{power}=2^{somePower}-1</math>, regrouping gives <math>2^n+k=2^{power}+2^{somePower}-1</math>.
 +
 +
Most importantly, realize that <math>power</math> can be from <math>0</math> to <math>n</math>, because of the restraints on <math>k</math> mentioned earlier. Same with <math>somePower</math>. Immediately at least one of <math>power</math> and <math>somePower</math> has to be <math>n</math>. If both were smaller, LHS is greater, contradiction. If both were greater, RHS is greater, contradiction.
 +
 +
Therefore, by setting one of <math>power</math> or <math>somePower</math> to <math>n</math>, we realize <math>k=2^{aCertainPower}-1</math>.
 +
 +
The conclusion is clear, right? Each <math>k</math> from <math>1</math> to <math>2^{n-1}-1</math> yields two distinct cases: one of <math>power</math> and <math>somePower</math> is equal to <math>n</math>, while the other is LESS THAN <math>n</math>. But for <math>k=2^n-1</math>, there is ONE CASE: BOTH values have to equal <math>n</math>. Therefore, the only <math>k</math> that has <math>f(2^n+k)</math> as odd must only be <math>2^n-1</math>, because the other ones yield a <math>f</math> of 1+1=0 in our mod. That proves our induction for a new power of 2, namely <math>n+1</math>, meaning that <math>f(number)</math> is only odd if <math>number = 2^{powerOfTwo} - 1</math>, and we are almost done...
 +
 +
Thus, the answer is <math>2^11-1=\boxed{2047}</math>.
 +
 +
This was pretty intuitive, and realizing quite <math>elementary</math> steps about how powers of 2 work gave us the solution! Estimated time: ~50 minutes. Cheers- expiLnCalc.
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 21:01, 8 April 2018

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_{power=0}^{pow_{larg}} f(n-2^{power})$, where $pow_{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^{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(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(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^{power}$ in the DS is equal to $2^{somePower} - 1$. Clearly $1 \leq k \leq 2^n - 1$.

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

Most importantly, realize that $power$ can be from $0$ to $n$, because of the restraints on $k$ mentioned earlier. Same with $somePower$. Immediately at least one of $power$ and $somePower$ 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 $power$ or $somePower$ to $n$, we realize $k=2^{aCertainPower}-1$.

The conclusion is clear, right? Each $k$ from $1$ to $2^{n-1}-1$ yields two distinct cases: one of $power$ and $somePower$ 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(number)$ is only odd if $number = 2^{powerOfTwo} - 1$, and we are almost done...

Thus, the answer is $2^11-1=\boxed{2047}$.

This was pretty intuitive, and realizing quite $elementary$ steps about how powers of 2 work gave us the solution! Estimated time: ~50 minutes. Cheers- expiLnCalc.

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=93856"