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

(Gave a vastly simpler and more intuitive alternate solution to the problem.)
(Corrected an error in my last edit and further developed logic behind its conclusion.)
Line 19: Line 19:
 
== Alternate Solution ==
 
== Alternate Solution ==
  
Notice that 2 is a prime factor of <math>I_k</math> if and only if <math>I_k</math> is even. Also notice that regardless of the positive integral value of <math>k</math>, dividing by <math>2^6</math> leaves us with a terminal digit of zero. Dividing by 2 again makes <math>I_k</math> odd, leaving us with the maximum value of <math>N(k) = \boxed{7}</math>
+
Notice that 2 is a prime factor of <math>I_k</math> if and only if <math>I_k</math> is even. Therefore, given any sufficiently high positive integral value of <math>k</math>, dividing <math>I_k</math> by <math>2^6</math> yields a terminal digit of zero, and dividing by 2 again leaves us with <math>2^7 * a = I_k</math> where <math>a</math> is an odd integer.
 +
Observe then that <math>\boxed{7}</math> must be the maximum value for <math>N(k)</math> because whatever value we choose for <math>k</math>, <math>N(k)</math> must be less than or equal to 7.
  
  

Revision as of 06:13, 22 December 2011

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\geq 5$ 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 $I_k$ if and only if $I_k$ 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 * a = I_k$ where $a$ is an odd integer. Observe then that $\boxed{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.


See Also

2009 AMC 12A (ProblemsAnswer KeyResources)
Preceded by
Problem 17
Followed by
Problem 19
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 12 Problems and Solutions
2009 AMC 10A (ProblemsAnswer KeyResources)
Preceded by
Problem 24
Followed by
Last Question
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
All AMC 10 Problems and Solutions