2006 AMC 12B Problems/Problem 22: Difference between revisions

Latest revision as of 14:52, 23 June 2021

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 we won't have any extra numbers from higher powers of $5$ . As we list out the powers of 5, it is clear that $5^{4}=625$ is less than 2006 and $5^{5}=3125$ is greater. Therefore, set $a$ and $b$ to be 624. Thus, c is $2006-(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*} \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*}$

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

@@ Line 1: / Line 1: @@
 == 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 ==
-* [[2006 AMC 12B Problems]]
+{{AMC12 box|year=2006|ab=B|num-b=21|num-a=23}}
+{{MAA Notice}}

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

Page

Toolbox

Search

2006 AMC 12B Problems/Problem 22: Difference between revisions

Latest revision as of 14:52, 23 June 2021

Contents

Problem

Solution 1

Solution 2

See also