Skip to main content

2006 AMC 12B Problem 22

Problem 22 of 25HarderNumber TheoryProblem-Solving Techniques

Suppose a,a, b,b, and cc are positive integers with a+b+c=2006,a + b + c = 2006, and a! b! c!=m⋅10n,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=∑k≥1(⌊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 ≥⌊20065k⌋−2.\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)−4⋅2=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.
AoPS wiki

Tagged: Legendre’s Formula · trailing zeros · optimization

More practice