Difference between revisions of "2013 USAJMO Problems/Problem 4"
Countingkg (talk | contribs) |
|||
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 be the number of ways to write as a sum of powers of , where we keep track of the order of the summation. For example, because can be written as , , , , , and . Find the smallest greater than for which is odd.
Solution
First of all, note that = where is the largest integer such that . We let for convenience.
From here, we proceed by induction, with our claim being that the only such that is odd are representable of the form
We induct on . It is trivially true for and . From here, we show that, if the only numbers where is odd are of the form described above, then the only numbers that are odd are of that form. We first consider all numbers , such that , going from the lower bound to the upper bound (a mini induction, you might say). We know that . For a number in this summation to be odd, . However, we know that , so must be equal to , or else cannot be in that interval. Now, from this, we know that , as . Therefore, and are distinct, and thus and are odd; since there are just two odd numbers, the ending sum for any is even. Finally, considering , the only odd number is , so the ending sum is odd.
The smallest greater than expressible as is The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.