Maths Olympiad Prep

Library / /280 of 310

, 2023

Number theory Difficulty 3.7 AMC 10/12 Find the answer Canada

If nn is a positive integer,
the symbol n!n! (which is read "nn factorial") represents the product of
the integers from 1 to nn,
inclusive. For example, 5!=(1)(2)(3)(4)(5)5!=(1)(2)(3)(4)(5) or 5!=1205!=120, which ends with exactly 1 zero.
For how many integers mm, with 1m301 \leq m \leq 30, is it possible to find
a value of nn so that n!n! ends with exactly mm zeros?

Pick one

Solution

If n!n! ends with exactly
mm zeroes, then n!n! is divisible by 10m10^m but not divisible by 10m+110^{m+1}. (If n!n! were divisible by 10m+110^{m+1}, it would end with at least
m+1m+1 zeroes.)

In this case, we can write $n! = 10^m \cdot
qwhere where q$ is not divisible
by 10. This in turn means that either qq is not divisible by 2 or not divisible
by 5 or both.

Since 2<52<5, when n2n \geq 2, the product $n! = 1 23\cdot 2 \cdot 3 \cdot \cdots \cdot (n-1)
\cdot n includes more multiples of 2 than of 5 among the nintegersinitsproduct,so integers in its product, so n!$ includes more factors of 2 than of
5.

This in turn means that, if n!n! ends
in exactly mm zeroes, then n!=10mqn! = 10^m \cdot q where qq is not divisible by 5, and so the
number of zeroes at the end of n!n!
is exactly equal to the number of prime factors of 5 in the prime
factorization of n!n!.

We note also that as nn increases,
the number of zeroes at the end of n!n! never decreases since the number of
factors of 5 either stays the same or increases as nn increases.

For n=1n=1 to n=4n=4, the product n!n! includes 0 multiples of 5, so n!n! ends in 0 zeroes.

For n=5n=5 to n=9n=9, the product n!n! includes 1 multiple of 5 (namely 5),
so n!n! ends in 1 zero.

For n=10n=10 to n=14n=14, the product n!n! includes 2 multiples of 5 (namely 5
and 10), so n!n! ends in 2
zeroes.

For n=15n=15 to n=19n=19, the product n!n! includes 3 multiples of 5 (namely 5,
10 and 15), so n!n! ends in 3
zeroes.

For n=20n=20 to n=24n=24, the product n!n! includes 4 multiples of 5 (namely 5,
10, 15, and 20), so n!n! ends in 4
zeroes.

For n=25n=25 to n=29n=29, the product n!n! includes 5 multiples of 5 (namely 5,
10, 15, 20, and 25) and includes 6 factors of 5 (since 25 contributes 2
factors of 5), so n!n! ends in 6
zeroes.

For n=30n=30 to n=34n=34, n!n! ends in 7 zeroes. For n=35n=35 to n=39n=39, n!n! ends in 8 zeroes.

For n=40n=40 to n=44n=44, n!n! ends in 9 zeroes. For n=45n=45 to n=49n=49, n!n! ends in 10 zeroes.

For n=50n=50 to n=54n=54, n!n! ends in 12 zeroes, since the product
n!n! includes 10 multiples of 5, two
of which include 2 factors of 5.

For n=55n=55 to n=74n=74, n!n! will end in 13, 14, 15, 16 zeroes as
nn increases.

For n=75n=75 to n=79n=79, n!n! ends in 18 zeroes.

For n=80n=80 to n=99n=99, n!n! ends in 19, 20, 21, 22 zeroes as nn increases.

For n=100n=100 to n=104n=104, n!n! ends in 24 zeroes.

For n=105n=105 to n=124n=124, n!n! ends in 25, 26, 27, 28 zeroes.

For n=125n=125, n!n! ends in 31 zeroes since 125125 includes 3 factors of 5, so 125!125! ends in 3 more zeroes than 124!124!.

Of the integers mm with 1m301 \leq m \leq 30, there is no value of
nn for which n!n! ends in mm zeroes when m=5,11,17,23,29,30m = 5, 11, 17, 23, 29, 30, which means
that 306=2430 - 6 = 24 of the values of
mm are possible.

Want a route through all this instead of an archive? The track puts 2,444 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.