Difference between revisions of "2006 AMC 12B Problems/Problem 22"
(→Solution 2) |
|||
(12 intermediate revisions by 9 users not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | Suppose <math>a</math>, <math>b</math> and <math>c</math> are positive integers with <math>a+b+c=2006</math>, and <math>a!b!c!=m\cdot 10^n</math>, where <math>m</math> and <math>n</math> are integers and <math>m</math> is not divisible by <math>10</math>. What is the smallest possible value of <math>n</math>? | ||
− | == Solution == | + | <math> |
+ | \mathrm{(A)}\ 489 | ||
+ | \qquad | ||
+ | \mathrm{(B)}\ 492 | ||
+ | \qquad | ||
+ | \mathrm{(C)}\ 495 | ||
+ | \qquad | ||
+ | \mathrm{(D)}\ 498 | ||
+ | \qquad | ||
+ | \mathrm{(E)}\ 501 | ||
+ | |||
+ | </math> | ||
+ | |||
+ | == 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 | ||
+ | it. Hence we are trying to minimize the power of <math>5</math> that will divide <math>a!b!c!</math>. | ||
+ | |||
+ | Consider <math>n! = 1\cdot 2 \cdot \dots \cdot n</math>. Each fifth term is divisible by <math>5</math>, each <math>25</math>-th one | ||
+ | by <math>25</math>, and so on. Hence the total power of <math>5</math> that divides <math>n</math> is <math>\left\lfloor \frac | ||
+ | n{5}\right\rfloor + | ||
+ | \left\lfloor \frac n{25}\right\rfloor + \cdots</math>. (For any <math>n</math> only finitely many terms in the sum | ||
+ | are | ||
+ | non-zero.) | ||
+ | |||
+ | In our case we have <math>a<2006</math>, so the largest power of <math>5</math> that will be less than <math>a</math> is at most | ||
+ | <math>5^4 = 625</math>. Therefore the power of <math>5</math> that divides <math>a!</math> is equal to <math>\left\lfloor \frac | ||
+ | a{5}\right\rfloor + | ||
+ | \left\lfloor \frac a{25}\right\rfloor + \left\lfloor \frac a{125}\right\rfloor + \left\lfloor \frac | ||
+ | a{625}\right\rfloor </math>. The same | ||
+ | is true for <math>b</math> and <math>c</math>. | ||
+ | |||
+ | Intuition may now try to lure us to split <math>2006</math> into <math>a+b+c</math> as evenly as possible, giving | ||
+ | <math>a=b=669</math> and <math>c=668</math>. However, this solution is not optimal. | ||
+ | |||
+ | To see how we can do better, let's rearrange the terms as follows: | ||
+ | |||
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | \text{result} | ||
+ | & = \Big\lfloor \frac a{5}\Big\rfloor + \Big\lfloor \frac b{5}\Big\rfloor + \Big\lfloor \frac | ||
+ | c{5}\Big\rfloor | ||
+ | \\ | ||
+ | & + \Big\lfloor \frac a{25}\Big\rfloor + \Big\lfloor \frac b{25}\Big\rfloor + \Big\lfloor \frac | ||
+ | c{25}\Big\rfloor | ||
+ | \\ | ||
+ | & + \Big\lfloor \frac a{125}\Big\rfloor + \Big\lfloor \frac b{125}\Big\rfloor + \Big\lfloor \frac | ||
+ | c{125}\Big\rfloor | ||
+ | \\ | ||
+ | & + \Big\lfloor \frac a{625}\Big\rfloor + \Big\lfloor \frac b{625}\Big\rfloor + \Big\lfloor \frac | ||
+ | c{625}\Big\rfloor | ||
+ | \end{align*} | ||
+ | </cmath> | ||
+ | |||
+ | The idea is that the rows of the above equation are roughly equal to <math>\left\lfloor \frac | ||
+ | n{5}\right\rfloor</math>, <math>\left\lfloor \frac n{25}\right\rfloor</math>, etc. | ||
+ | |||
+ | More precisely, we can now notice that for any positive integers <math>a,b,c,k</math> we can write <math>a,b,c</math> in the form <math>a=a_0k | ||
+ | + a_1</math>, <math>b=b_0k+b_1</math>, <math>c=c_0k + c_1</math>, where all <math>a_i,b_i,c_i</math> are integers and <math>0\leq | ||
+ | a_1,b_1,c_1<k</math>. | ||
+ | |||
+ | It follows that | ||
+ | <cmath>\Big\lfloor \frac a{k}\Big\rfloor + \Big\lfloor \frac b{k}\Big\rfloor + \Big\lfloor \frac | ||
+ | c{k}\Big\rfloor = a_0+b_0+c_0</cmath> | ||
+ | and | ||
+ | <cmath>\Big\lfloor \frac {a+b+c}k\Big\rfloor = a_0 + b_0 + c_0 + \Big\lfloor \frac | ||
+ | {a_1+b_1+c_1}k\Big\rfloor \leq a_0 + b_0 + c_0 + 2 </cmath> | ||
+ | |||
+ | Hence we get that for any positive integers <math>a,b,c,k</math> we have | ||
+ | <cmath> | ||
+ | \Big\lfloor \frac a{k}\Big\rfloor + \Big\lfloor \frac b{k}\Big\rfloor + \Big\lfloor \frac | ||
+ | c{k}\Big\rfloor | ||
+ | \quad | ||
+ | \geq | ||
+ | \quad | ||
+ | \Big\lfloor \frac {a+b+c}k\Big\rfloor - 2 | ||
+ | </cmath> | ||
+ | |||
+ | Therefore for any <math>a,b,c</math> the result is at least <math>\left\lfloor \frac n{5}\right\rfloor + | ||
+ | \left\lfloor \frac n{25}\right\rfloor + \left\lfloor \frac n{125}\right\rfloor + | ||
+ | \left\lfloor \frac n{625}\right\rfloor - 8 = 401 + 80 + 16 + 3 - 8 = 500 - 8 = 492</math>. | ||
+ | |||
+ | If we now show how to pick <math>a,b,c</math> so that we'll get the result <math>492</math>, we will be done. | ||
+ | |||
+ | Consider the row with <math>625</math> in the denominator. We need to achieve sum <math>1</math> in this row, | ||
+ | hence we need to make two of the numbers smaller than <math>625</math>. Choosing <math>a=b=624</math> | ||
+ | does this, and it will give us the largest possible remainders for <math>a</math> and <math>b</math> in | ||
+ | the other three rows, so this is a pretty good candidate. We can compute | ||
+ | <math>c=2006-a-b=758</math> and verify that this triple gives the desired result <math>\boxed{492}</math>. | ||
== 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.