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