# Difference between revisions of "2009 AMC 12A Problems/Problem 18"

The following problem is from both the 2009 AMC 12A #18 and 2009 AMC 10A #25, so both problems redirect to this page.

## Problem

For $k > 0$, let $I_k = 10\ldots 064$, where there are $k$ zeros between the $1$ and the $6$. Let $N(k)$ be the number of factors of $2$ in the prime factorization of $I_k$. What is the maximum value of $N(k)$? $\textbf{(A)}\ 6\qquad \textbf{(B)}\ 7\qquad \textbf{(C)}\ 8\qquad \textbf{(D)}\ 9\qquad \textbf{(E)}\ 10$

## Solution

The number $I_k$ can be written as $10^{k+2} + 64 = 5^{k+2}\cdot 2^{k+2} + 2^6$.

For $k\in\{1,2,3\}$ we have $I_k = 2^{k+2} \left( 5^{k+2} + 2^{4-k} \right)$. The first value in the parentheses is odd, the second one is even, hence their sum is odd and we have $N(k)=k+2\leq 5$.

For $k>4$ we have $I_k=2^6 \left( 5^{k+2}\cdot 2^{k-4} + 1 \right)$. For $k>4$ the value in the parentheses is odd, hence $N(k)=6$.

This leaves the case $k=4$. We have $I_4 = 2^6 \left( 5^6 + 1 \right)$. The value $5^6 + 1$ is obviously even. And as $5\equiv 1 \pmod 4$, we have $5^6 \equiv 1 \pmod 4$, and therefore $5^6 + 1 \equiv 2 \pmod 4$. Hence the largest power of $2$ that divides $5^6+1$ is $2^1$, and this gives us the desired maximum of the function $N$: $N(4) = \boxed{7}$.

## Alternate Solution

Notice that 2 is a prime factor of an integer $n$ if and only if $n$ is even. Therefore, given any sufficiently high positive integral value of $k$, dividing $I_k$ by $2^6$ yields a terminal digit of zero, and dividing by 2 again leaves us with $2^7 \cdot a = I_k$ where $a$ is an odd integer. Observe then that $\boxed{\textbf{(B)}7}$ must be the maximum value for $N(k)$ because whatever value we choose for $k$, $N(k)$ must be less than or equal to $7$.

"Isn't this solution incomplete because we need to show that $N(k) = 7$ can be reached?"

An example of 7 being reached is 1000064. 1000064 divided by $2^7=128$ is 7813.

In fact, 1000064 is the ONLY $N(k)$ that satisfies 7. All others are 6 or lower, because if there are more zeroes, to be divisible by 128 (\$2^7), the last 7 digits must be divisible by 128, but 64 isn't. Meanwhile, if there are less zeroes, we can test by division that they do not work.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 