2015 AMC 10B Problem 23

P21-25~7 minPrint

Divisibility & Factors Primes Bound the quantity above/below or estimate to pin it down Organized listing / direct enumeration

Let $n$ be a positive integer greater than 4 such that the decimal representation of $n!$ ends in $k$ zeros and the decimal representation of $(2n)!$ ends in $3k$ zeros. Let $s$ denote the sum of the four least possible values of $n$ . What is the sum of the digits of $s$ ?

Show solution without answering

Key insight

End zeros come from factors of 5. Doubling n usually just doubles them, so list small n and find the few that triple: 8, 9, 13, 14.

Solution

Step 1: what makes the zeros? Each zero at the end of a number comes from a factor $10 = 2 \cdot 5$ . A factorial has many more $2$ s than $5$ s, so the number of end zeros equals the number of factors of $5$ .

For numbers below $50$ , count the factors of $5$ like this: one for each multiple of $5$ , plus one more for $25$ (because $25 = 5 \cdot 5$ ). For example, $28!$ contains $5, 10, 15, 20, 25$ , which is $5$ multiples, plus the extra $5$ from $25$ : $6$ zeros.

Step 2: why it is hard. Going from $n!$ to $(2n)!$ roughly doubles the number of multiples of $5$ . To triple the zeros, $(2n)!$ needs something extra. There are two ways to get it: a lucky jump, like $8!$ having only one multiple of $5$ while $16!$ has three; or the second $5$ inside $25$ , which $(2n)!$ gets once $2n \ge 25$ . Both happen only for small $n$ , so a table will find the answers quickly.

Step 3: make a table. Start at $n = 5$ and go up. Write $k$ for the zeros of $n!$ .

$n$	zeros in $n!$ ( $k$ )	$2n$	zeros in $(2n)!$	equals $3k$ ?
$5, 6, 7$	$1$	$10, 12, 14$	$2$	no
$8, 9$	$1$	$16, 18$	$3$	yes
$10, 11, 12$	$2$	$20, 22, 24$	$4$	no
$13, 14$	$2$	$26, 28$	$5 + 1 = 6$	yes

We checked every $n$ from $5$ up, in order, so the four smallest values are $8, 9, 13, 14$ .

Step 4: finish. $s = 8 + 9 + 13 + 14 = 44$ , and its digits add to $4 + 4 = 8$ .

The answer is $\boxed{\textbf{(B)}\ 8}$ .

Why this works

Zeros at the end of a factorial are only about the prime $5$ : count the multiples of $5$ , then add one more for each multiple of $25$ , and so on. Doubling $n$ usually just doubles that count, so tripling it needs an extra, either from how the multiples of $5$ happen to fall or from the second $5$ in $25$ . A short table is quicker than trying to solve this with algebra.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Factorials have far more factors of $2$ than $5$ , so the number of trailing zeros of $m!$ is the number of factors of $5$ :
$Z(m) = \left\lfloor \frac{m}{5} \right\rfloor + \left\lfloor \frac{m}{25} \right\rfloor + \cdots$
We need $Z(2n) = 3\,Z(n)$ with $n \ge 5$ .

Roughly, $Z(2n) \approx 2\,Z(n)$ , so tripling needs $(2n)!$ to gain extra fives, either from the rounding in $\lfloor 2n/5 \rfloor$ or from multiples of $25$ that $n!$ lacks. For $n < 25$ , $Z(n) = \lfloor n/5 \rfloor$ , while $Z(2n) = \lfloor 2n/5 \rfloor + \lfloor 2n/25 \rfloor$ . Tabulate by the block of $n$ :

$n = 5, 6, 7$ : $Z(n) = 1$ , $Z(2n) = Z(10), Z(12), Z(14) = 2$ . No.
$n = 8, 9$ : $Z(n) = 1$ , $Z(16) = Z(18) = 3$ . Yes.
$n = 10, 11, 12$ : $Z(n) = 2$ , $Z(20) = Z(22) = Z(24) = 4$ . No.
$n = 13, 14$ : $Z(n) = 2$ , $Z(26) = Z(28) = 6$ . Yes.

Four values found: $8, 9, 13, 14$ , and they are the least since we checked every $n \ge 5$ in order. Hence
$s = 8 + 9 + 13 + 14 = 44,$
whose digit sum is $4 + 4 = 8$ .

The answer is $\boxed{\textbf{(B)}\ 8}$ .

Review in the AoPS books

Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
Introduction to Number Theory, Chapter 2: Primes and Composites
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
Introduction to Number Theory, Chapter 5: Divisor Problems (§5.2, §5.3)