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 "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 12:00, 5 July 2015

Problem

Suppose $a$, $b$ and $c$ are positive integers with $a+b+c=2006$, and $a!b!c!=m\cdot 10^n$, where $m$ and $n$ are integers and $m$ is not divisible by $10$. What is the smallest possible value of $n$?

$\mathrm{(A)}\ 489 \qquad \mathrm{(B)}\ 492 \qquad \mathrm{(C)}\ 495 \qquad \mathrm{(D)}\ 498 \qquad \mathrm{(E)}\ 501$

Solution 1

The power of 10 for any factorial is given by the well-known algorithm \[\left\lfloor \frac n{5}\right\rfloor + \left\lfloor \frac n{25}\right\rfloor + \left\lfloor \frac n{125}\right\rfloor + \cdots\] 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 $5^{4}=625$ is less than 2008 and $5^{5}=3125$ is greater. Therefore, set $a$ and $b$ to be 624. Thus, c is $2008-(624\cdot 2)=758$. Applying the algorithm, we see that our answer is $152+152+188= \boxed{492}$.

Solution 2

Clearly, the power of $2$ that divides $n!$ is larger or equal than the power of $5$ which divides it. Hence we are trying to minimize the power of $5$ that will divide $a!b!c!$.

Consider $n! = 1\cdot 2 \cdot \dots \cdot n$. Each fifth term is divisible by $5$, each $25$-th one by $25$, and so on. Hence the total power of $5$ that divides $n$ is $\left\lfloor \frac n{5}\right\rfloor + \left\lfloor \frac n{25}\right\rfloor + \cdots$. (For any $n$ only finitely many terms in the sum are non-zero.)

In our case we have $a<2006$, so the largest power of $5$ that will be less than $a$ is at most $5^4 = 625$. Therefore the power of $5$ that divides $a!$ is equal to $\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$. The same is true for $b$ and $c$.

Intuition may now try to lure us to split $2006$ into $a+b+c$ as evenly as possible, giving $a=b=669$ and $c=668$. However, this solution is not optimal.

To see how we can do better, let's rearrange the terms as follows:

\begin{align*} 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*}

The idea is that the rows of the above equation are roughly equal to $\left\lfloor \frac n{5}\right\rfloor$, $\left\lfloor \frac n{25}\right\rfloor$, etc.

More precisely, we can now notice that for any positive integers $a,b,c,k$ we can write $a,b,c$ in the form $a=a_0k + a_1$, $b=b_0k+b_1$, $c=c_0k + c_1$, where all $a_i,b_i,c_i$ are integers and $0\leq a_1,b_1,c_1<k$.

It follows that \[\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\] and \[\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\]

Hence we get that for any positive integers $a,b,c,k$ we have \[\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\]

Therefore for any $a,b,c$ the result is at least $\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$.

If we now show how to pick $a,b,c$ so that we'll get the result $492$, we will be done.

Consider the row with $625$ in the denominator. We need to achieve sum $1$ in this row, hence we need to make two of the numbers smaller than $625$. Choosing $a=b=624$ does this, and it will give us the largest possible remainders for $a$ and $b$ in the other three rows, so this is a pretty good candidate. We can compute $c=2006-a-b=758$ and verify that this triple gives the desired result $\boxed{492}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_AMC_12B_Problems/Problem_22&oldid=70997"