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

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

m (→‎Solution)
(Gave a vastly simpler and more intuitive alternate solution to the problem.)
Line 15: Line 15:
  
 
This leaves the case <math>k=4</math>. We have <math>I_4 = 2^6 \left( 5^6 + 1 \right)</math>. The value <math>5^6 + 1</math> is obviously even. And as <math>5\equiv 1 \pmod 4</math>, we have <math>5^6 \equiv 1 \pmod 4</math>, and therefore <math>5^6 + 1 \equiv 2 \pmod 4</math>. Hence the largest power of <math>2</math> that divides <math>5^6+1</math> is <math>2^1</math>, and this gives us the desired maximum of the function <math>N</math>: <math>N(4) = \boxed{7}</math>.
 
This leaves the case <math>k=4</math>. We have <math>I_4 = 2^6 \left( 5^6 + 1 \right)</math>. The value <math>5^6 + 1</math> is obviously even. And as <math>5\equiv 1 \pmod 4</math>, we have <math>5^6 \equiv 1 \pmod 4</math>, and therefore <math>5^6 + 1 \equiv 2 \pmod 4</math>. Hence the largest power of <math>2</math> that divides <math>5^6+1</math> is <math>2^1</math>, and this gives us the desired maximum of the function <math>N</math>: <math>N(4) = \boxed{7}</math>.
 +
 +
 +
== 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>
 +
  
 
== See Also ==
 
== See Also ==

Revision as of 06:42, 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. Also notice that regardless of the positive integral value of $k$, dividing by $2^6$ leaves us with a terminal digit of zero. Dividing by 2 again makes $I_k$ odd, leaving us with the maximum value of $N(k) = \boxed{7}$


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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12A_Problems/Problem_18&oldid=43834"