2006 AMC 12B Problems/Problem 22

From AoPSWiki

Revision as of 10:24, 12 February 2009 by Misof (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

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

Obviously 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 \fracn{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$ , hence 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 \fraca{5}\right\rfloor +\left\lfloor \frac a{25}\right\rfloor + \left\lfloor \frac a{125}\right\rfloor + \left\l...$ . 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=668$ and $c=669$ . 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 \fracc{5}\Big...$

The idea is that the rows of the above equation are roughly equal to $\left\lfloor \fracn{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\leqa_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 \fracc{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 \fracc{k}\Big\rfloor\quad\geq\quad\Big\lf...$

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\l...$ .

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}$ .

2006 AMC 12B (Problems • 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

Personal tools

Navigation

Search

Toolbox

2006 AMC 12B Problems/Problem 22

From AoPSWiki

Problem

Solution

See also