Manhattan Challenge Problem of the week! - 04/30/07

How many terminating zeroes does 200! have?

(A) 40
(B) 48
(C) 49
(D) 55
(E) 64

Answer : C

OE - To determine how many terminating zeroes a number has, we need to determine how many times the number can be divided evenly by 10. (For example, the number 404000 can be divided evenly by 10 three times, as follows:

404000/10 = 40400
40400/10 = 4040
4040/10 = 404

We can see that the number has three terminating zeroes because it is divisible by 10 three times.) Thus, to arrive at an answer, we need to count the factors of 10 in 200! Recall that

200! = 200 * 199 * 198 ........... * 4 * 3 * 2 * 1

Each factor of 10 consists of one prime factor of 2 and one prime factor of 5. Let’s start by counting the factors of 5 in 200!. Starting from 1, we get factors of 5 at 5, 10, 15, . . . , 190, 195, and 200, or every 5th number from 1 to 200. Thus, there are 200/5 or 40 numbers divisible by five from 1 to 200. Therefore, there are at least 40 factors of 5 in 200!.

We cannot stop counting here, because some of those multiples of 5 contribute more than just one factor of 5. Specifically, any multiple of 52 (or 25) and any multiple of 53 (or 125) contribute additional factors of 5. There are 8 multiples of 25 (namely, 25, 50, 75, 100, 125, 150, 175, 200). Each of these 8 numbers contributes one additional factor of 5 (in addition to the one we already counted) so we now have counted 40 + 8, or 48 factors of 5. Finally, 125 contributes a third additional factor of 5, so we now have 48 + 1 or 49 total factors of 5 in 200!.

Let us now examine the factors of 2 in 200!. Since every even number contributes at least one factor of 2, there are at least 100 factors of 2 in 200! (2, 4, 6, 8 . . .etc). Since we are only interested in the factors of 10 — a factor of 2 paired with a factor of 5 — and there are more factors of 2 than there are of 5, the number of factors of 10 is constrained by the number of factors of 5. Since there are only 49 factors of 5, each with an available factor of 2 to pair with, there are exactly 49 factors of 10 in 200!.

It follows that 200! has 49 terminating zeroes, and the correct answer is C.