2009 AMC 10A Problem 25

The number $1\underbrace{0\ldots0}_{k}64$ has $k + 3$ digits, so
$$I_k = 10^{k+2} + 64 = 2^{k+2} \cdot 5^{k+2} + 2^6.$$

Compare the exponents $k + 2$ and $6$.

Case $k < 4$ ($k + 2 < 6$): factor out $2^{k+2}$:
$$I_k = 2^{k+2}\left(5^{k+2} + 2^{4-k}\right).$$
The bracket is odd plus even, hence odd, so $N(k) = k + 2 \le 5$.

Case $k > 4$ ($k + 2 > 6$): factor out $2^6$:
$$I_k = 2^6\left(2^{k-4} \cdot 5^{k+2} + 1\right).$$
The bracket is even plus one, hence odd, so $N(k) = 6$.

Case $k = 4$: the powers tie, and
$$I_4 = 2^6\left(5^6 + 1\right) = 2^6 \cdot 15626 = 2^6 \cdot 2 \cdot 7813 = 2^7 \cdot 7813.$$
Since $7813$ is odd, $N(4) = 7$.

The maximum is $7$, attained only at $k = 4$.

The answer is $\boxed{\textbf{(B)}\ 7}$.

For a sum of two powers of $2$ times odd numbers, the exponent of $2$ is the smaller of the two exponents, unless they are equal, in which case the odd parts add to an even number and the exponent jumps by at least one. The "equal exponents" case is where the action is; here $5^6 + 1 = 15626$ contributes exactly one more factor of $2$.

Test directly: $I_1 = 1064 = 2^3 \cdot 133$, $I_2 = 10064 = 2^4 \cdot 629$, $I_3 = 100064 = 2^5 \cdot 3127$, $I_4 = 1000064 = 2^7 \cdot 7813$, $I_5 = 10000064 = 2^6 \cdot 156251$. The value $7$ at $k = 4$ stands out, and the general argument shows $N(k) = 6$ for all larger $k$.

• Concluding the maximum is 6 because 2^6 = 64 divides I_k for large k, without testing the boundary case k = 4 where 5^6 + 1 is even.
• Miscounting the digits and writing $I_k = 10^{k+1} + 64$ or $10^{k+3} + 64$, which shifts the special case to the wrong $k$.