[Soln] Fall 2014 USA Online Math Open Qn 9

Fall 2014 USA OMO Qn 9. Let N = 2014! + 2015! + 2016! + \dots + 9999!. How many zeros are at the end of the decimal representation of N?

To count the number of zeros at the end of N, we need to find out the highest power of 2 that divides N and the highest power of 5 that divides N, then the number of zeros that the decimal representation of N has is the lower of the two. Concretely, if N = 2^\alpha 5^\beta M for some integer M such that \gcd (M, 10) = 1, then the number of zeros in N‘s decimal representation is \min (\alpha, \beta).

The short explanation above suggests that it would be a good idea to find the prime factorisation of N. The key to the solution is realising that each succeeding term is a multiple of the previous one, hence all succeeding terms are a multiple of the first one. That is, we can write N as

N = 2014! [ 1 + 2015 + (2015)(2016) + \dots + (2015)(2016)\dots(9999) ].

At this point, you might notice that for the second factor (the one in square brackets), all its terms except the 1 in front are divisible by 5. This means that the second factor will not be “contributing” any factors of 5 to the prime factorisation of N. To simply the line above, we can write

N = 2014! [1 + 5k]

for some integer k. While [1+5k] factor might contribute some factors of 2 to the prime factorisation of N, it won’t contribute any more factors of 5. It should also be clear that the 2014! factor has more factors of 2 than factors of 5. Hence,

\text{number of '0's at end of }N = \text{number of '0's at end of } 2014!.

There is a well-known formula that the highest power of a prime p which divides n! is

\displaystyle\sum_{i = 1}^\infty \left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \displaystyle\frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dots

Hence, number of ‘0’s at the end of N is

\begin{aligned} \left\lfloor \frac{2014}{5} \right\rfloor + \left\lfloor \frac{2014}{25} \right\rfloor + \left\lfloor \frac{2014}{125} \right\rfloor + \left\lfloor \frac{2014}{625} \right\rfloor &= 402 + 80 + 16 + 3 \\  &= \boldsymbol{501}. \end{aligned}

The answer is 501.

Advertisements
This entry was posted in USA and tagged , , . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s