Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2009 AMC 12A Problems/Problem 18

Revision as of 16:03, 2 October 2016 by PenguinJoe (talk | contribs) (→‎Solution)
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^{k-4} \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 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$.

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

See Also

2009 AMC 12A (Problems • Answer Key • Resources)
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 (Problems • Answer Key • Resources)
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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12A_Problems/Problem_18&oldid=80490"