Skip to main content

2006 AMC 12B Problem 22

Problem 22 of 25HarderAlgebraNumber Theory

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

Answer choices

Show solution

Solution

Since factors of 22 are more plentiful than factors of 5,5, nn equals the number of factors of 55 in a!b!c!,a!\,b!\,c!, namely n=k1(a5k+b5k+c5k).n = \sum_{k \ge 1}\left(\left\lfloor \tfrac{a}{5^k}\right\rfloor + \left\lfloor \tfrac{b}{5^k}\right\rfloor + \left\lfloor \tfrac{c}{5^k}\right\rfloor\right). For each k,k, a5k+b5k\lfloor \frac{a}{5^k} \rfloor + \lfloor \frac{b}{5^k} \rfloor +c5k+ \lfloor \frac{c}{5^k} \rfloor 20065k2.\ge \lfloor \frac{2006}{5^k} \rfloor - 2. Summing over k=1,2,3,4k = 1, 2, 3, 4 (as 2006<552006 \lt 5^5) gives n(401+80+16+3)42=492. \begin{aligned} &n \ge (401 + 80 + 16 + 3) \\ &\quad {}- 4 \cdot 2 = 492. \end{aligned} Equality is attainable, for example with a=b=624a = b = 624 and c=758.c = 758. So the minimum is 492.492. Thus, the correct answer is B.

More practice

Concepts: Legendre’s Formula · trailing zeros · optimization

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.