2009 AMC 10A Problem 25

1. Write out a few: $I_1 = 1064$, $I_2 = 10064$, $I_3 = 100064$. In general, $I_k$ is $1$ followed by $k + 2$ more digits, so
$$I_k = 10^{k+2} + 64 = 2^{k+2} \times 5^{k+2} + 2^6.$$
2. Both parts have factors of $2$. Pull out as many $2$s as both parts share and see whether what is left is odd.
3. Small $k$ ($k = 1, 2, 3$). Here $k + 2$ is less than $6$. Pull out $2^{k+2}$:
$$I_k = 2^{k+2}\left(5^{k+2} + 2^{4-k}\right).$$
Inside the bracket: odd plus even is odd. So $N(k) = k + 2$, which is $3, 4, 5$.
4. Large $k$ ($k \ge 5$). Here $k + 2$ is more than $6$. Pull out $2^6$:
$$I_k = 2^6\left(2^{k-4} \times 5^{k+2} + 1\right).$$
Inside: even plus $1$ is odd. So $N(k) = 6$.
5. The tie, $k = 4$. Both parts have exactly $2^6$:
$$I_4 = 2^6\left(5^6 + 1\right) = 2^6 \times 15626.$$
Now the bracket is odd plus odd, which is even. $15626 = 2 \times 7813$, and $7813$ is odd. So $I_4 = 2^7 \times 7813$ and $N(4) = 7$.
6. The largest value is $7$.

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

When you add two numbers with different numbers of factors of $2$, the sum has the smaller number of $2$s. Only when the counts are equal can the sum pick up extra $2$s, because odd plus odd is even. So always check the case where the two counts tie; that is where the maximum hides.

Divide by $2$ as long as you can:
- $I_1 = 1064 = 2^3 \times 133$
- $I_2 = 10064 = 2^4 \times 629$
- $I_3 = 100064 = 2^5 \times 3127$
- $I_4 = 1000064 = 2^7 \times 7813$
- $I_5 = 10000064 = 2^6 \times 156251$

The value $7$ at $k = 4$ stands out, and step 4 above shows $N(k)$ stays at $6$ for all larger $k$.

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}$.