Difference between revisions of "2006 AMC 12B Problems/Problem 22"
m (→Solution) |
(→Solution 2) |
||
(7 intermediate revisions by 5 users not shown) | |||
Line 12: | Line 12: | ||
\qquad | \qquad | ||
\mathrm{(E)}\ 501 | \mathrm{(E)}\ 501 | ||
+ | |||
</math> | </math> | ||
− | == Solution == | + | == Solution 1== |
+ | The power of <math>10</math> 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 <math>5</math> because we won't have any extra numbers from higher powers of <math>5</math>. As we list out the powers of 5, it is clear that <math>5^{4}=625</math> is less than 2006 and <math>5^{5}=3125</math> is greater. Therefore, set <math>a</math> and <math>b</math> to be 624. Thus, c is <math>2006-(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>. | ||
Line 40: | Line 47: | ||
<cmath> | <cmath> | ||
\begin{align*} | \begin{align*} | ||
− | result | + | \text{result} |
& = \Big\lfloor \frac a{5}\Big\rfloor + \Big\lfloor \frac b{5}\Big\rfloor + \Big\lfloor \frac | & = \Big\lfloor \frac a{5}\Big\rfloor + \Big\lfloor \frac b{5}\Big\rfloor + \Big\lfloor \frac | ||
c{5}\Big\rfloor | c{5}\Big\rfloor | ||
Line 93: | Line 100: | ||
== See also == | == See also == | ||
{{AMC12 box|year=2006|ab=B|num-b=21|num-a=23}} | {{AMC12 box|year=2006|ab=B|num-b=21|num-a=23}} | ||
+ | {{MAA Notice}} |
Latest revision as of 15:52, 23 June 2021
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 for any factorial is given by the well-known algorithm
It is rational to guess numbers right before powers of
because we won't have any extra numbers from higher powers of
. As we list out the powers of 5, it is clear that
is less than 2006 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.