Problem:
There exists a unique strictly increasing sequence of nonnegative integers a1<a2<⋯<ak such that
217+12289+1=2a1+2a2+⋯+2ak
What is k?
Answer Choices:
A. 117
B. 136
C. 137
D. 273
E. 306
Solution:
First, substitute 217 with x. Then, the given equation becomes
x+1x17+1=x16−x15+x14…−x1+x0
by sum of powers factorization. Now consider only x16−x15. This equals
x15(x−1)=x15⋅(217−1)
Note that 217−1 equals 216+215+…+1, by difference of powers factorization (or by considering the expansion of 217=216+215+…+2+2). Thus, we can see that x16−x15 forms the sum of 17 different powers of 2. Applying the same method to each of
x14−x13,x12−x11,…,x2−x1
we can see that each of the pairs forms the sum of 17 different powers of 2. This gives us 17⋅8=136. But we must count also the x0 term. Thus, Our answer is 136+1=(C) 137.
OR
Multiply both sides by 217+1 to get
2289+1=2a1+2a2+…+2ak+2a1+17+2a2+17+…+2ak+17
Notice that a1=0, since there is a 1 on the LHS. However, now we have an extra term of 218 on the right from 2a1+17. To cancel it, we let a2=18. The two 218's now combine into a term of 219, so we let a3=19. And so on, until we get to a18=34. Now everything we don't want telescopes into 235.
We already have that term since we let
a2=18⟹a2+17=35
Everything from now on will automatically telescope to 252. So we let a19 be 52.
As you can see, we will have to add 17an′s at a time, then "wait" for the sum to automatically telescope for the next 17 numbers, etc, until we get to 2289. We only need to add an′s between odd multiples of 17 and even multiples. The largest even multiple of 17 below 289 is 17⋅16, so we will have to add a total of 17⋅8an′s. However, we must not forget we let a1=0 at the beginning, so our answer is
17⋅8+1=(C) 137
The problems on this page are the property of the MAA's American Mathematics Competitions