Difference between revisions of "2009 AMC 12A Problems/Problem 18"
(→Solution 3) |
m (→Alternate Solution) |
||
Line 16: | Line 16: | ||
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>. | ||
− | == | + | == Solution 2 == |
Notice that 2 is a prime factor of an integer <math>n</math> if and only if <math>n</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 \cdot a = I_k</math> where <math>a</math> is an odd integer. | Notice that 2 is a prime factor of an integer <math>n</math> if and only if <math>n</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 \cdot a = I_k</math> where <math>a</math> is an odd integer. |
Revision as of 22:27, 17 January 2019
- 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 , let
, where there are
zeros between the
and the
. Let
be the number of factors of
in the prime factorization of
. What is the maximum value of
?
Solution
The number can be written as
.
For we have
. The first value in the parentheses is odd, the second one is even, hence their sum is odd and we have
.
For we have
. For
the value in the parentheses is odd, hence
.
This leaves the case . We have
. The value
is obviously even. And as
, we have
, and therefore
. Hence the largest power of
that divides
is
, and this gives us the desired maximum of the function
:
.
Solution 2
Notice that 2 is a prime factor of an integer if and only if
is even. Therefore, given any sufficiently high positive integral value of
, dividing
by
yields a terminal digit of zero, and dividing by 2 again leaves us with
where
is an odd integer.
Observe then that
must be the maximum value for
because whatever value we choose for
,
must be less than or equal to
.
"Isn't this solution incomplete because we need to show that can be reached?"
An example of 7 being reached is 1000064. 1000064 divided by is 7813.
In fact, 1000064 is the ONLY that satisfies 7. All others are 6 or lower, because if there are more zeroes, to be divisible by 128 (
), 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.
Solution 3
As in the first solution, the number can be written as
. Factor
out of the expression to get
.
You can now easily see that is divisible by at least 6 factors of two, from
. Any other factors of two will come from the expression
.
Make the substitution: .
You now have
, so the expression becomes
This is valid when
.
Obviously, if is negative, the expression will be fractional and not contain any extra factors of two.
If , the value
will end in a zero. When 1 is added to the expression, the expression will end in 1. Since numbers divisible by 2 end in 0,2,4,6, or 8, the expression is not divisible by 2 and will not contribute to the total.
If , the expression evaluates to
. Dividing out twos, you find that this value is only divisible by one factor of 2.
The six factors of two from earlier add to this factor of two to give
Solution written by coolak
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.