Difference between revisions of "2006 AMC 12B Problems/Problem 22"
(→Solution) |
|||
Line 14: | Line 14: | ||
</math> | </math> | ||
− | == Solution == | + | == Solution 1== |
+ | The power of 10 for any factorial is given by the well-known algorithm | ||
+ | <cmath>\left\lfloor \frac | ||
+ | n{5}\right\rfloor + | ||
+ | \left\lfloor \frac n{25}\right\rfloor + \left\lfloor \frac n{125}\right\rfloor + \cdots</cmath> | ||
+ | It is rational to guess numbers right before powers of 5 because then, we won't have any extra values from higher powers of 5. As we list out the powers of 5, it is clear that <math>5^{4}=625</math> is less than 2008 and <math>5^{5}=3125</math> is greater. Therefore, set <math>a</math> and <math>b</math> to be 624. Thus, c is <math>2008-(624\cdot 2)=758</math>. Applying the algorithm, we see that our answer is <math>152+152+188= \boxed{492}</math>. | ||
+ | == Solution 2== | ||
Clearly, the power of <math>2</math> that divides <math>n!</math> is larger or equal than the power of <math>5</math> which divides | Clearly, the power of <math>2</math> that divides <math>n!</math> is larger or equal than the power of <math>5</math> which divides | ||
it. Hence we are trying to minimize the power of <math>5</math> that will divide <math>a!b!c!</math>. | it. Hence we are trying to minimize the power of <math>5</math> that will divide <math>a!b!c!</math>. |
Revision as of 13:00, 5 July 2015
Contents
Problem
Suppose ,
and
are positive integers with
, and
, where
and
are integers and
is not divisible by
. What is the smallest possible value of
?
Solution 1
The power of 10 for any factorial is given by the well-known algorithm
It is rational to guess numbers right before powers of 5 because then, we won't have any extra values from higher powers of 5. As we list out the powers of 5, it is clear that
is less than 2008 and
is greater. Therefore, set
and
to be 624. Thus, c is
. Applying the algorithm, we see that our answer is
.
Solution 2
Clearly, the power of that divides
is larger or equal than the power of
which divides
it. Hence we are trying to minimize the power of
that will divide
.
Consider . Each fifth term is divisible by
, each
-th one
by
, and so on. Hence the total power of
that divides
is
. (For any
only finitely many terms in the sum
are
non-zero.)
In our case we have , so the largest power of
that will be less than
is at most
. Therefore the power of
that divides
is equal to
. The same
is true for
and
.
Intuition may now try to lure us to split into
as evenly as possible, giving
and
. However, this solution is not optimal.
To see how we can do better, let's rearrange the terms as follows:
The idea is that the rows of the above equation are roughly equal to ,
, etc.
More precisely, we can now notice that for any positive integers we can write
in the form
,
,
, where all
are integers and
.
It follows that
and
Hence we get that for any positive integers we have
Therefore for any the result is at least
.
If we now show how to pick so that we'll get the result
, we will be done.
Consider the row with in the denominator. We need to achieve sum
in this row,
hence we need to make two of the numbers smaller than
. Choosing
does this, and it will give us the largest possible remainders for
and
in
the other three rows, so this is a pretty good candidate. We can compute
and verify that this triple gives the desired result
.
See also
2006 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 21 |
Followed by Problem 23 |
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.