Friday, December 22, 2006

Brain Damage

Again, Kimota94 provided the first (and this time, only) correct response to the last math problems. Congratulations - go here to see his solution.

Here's a new problem for the holidays:

How many zeros are at the end of 1000! ?

(for those unaware of the ! operator - it is read "factorial". n! means the product of all numbers from 1 to n. e.g. 4! = 1*2*3*4 = 24)

5 comments:

cjg said...

I have an answer, but I used the tools at my disposal - i.e. brute force. I'll express it as a formula so that casual readers can skip over it: (2^8)-(2^3 - 1).

Kimota94 aka Matt said...

I'm not sure if I'm on the right track, and I didn't look at cjg's response (so as not to influence my own). Here's the approach I took.

When multiplying 1000*999*998...*2*1, it seems that the number of zeroes at the end is only increased if the new multiplier ends with a digit of 0, or ends with a digit of 5 and the current multiplicand has, as its last non-zero digit, an even digit. Treating those as two different cases:

1)a) 1000 (the original multiplicand) will contribute 3 zeroes;
b) 900,800,...100 will each contribute 2 zeroes, for a total of 18 zeroes
c) 990,980,...10 (skipping the hundreds) will each contribute 1 zero, for a total of 90 zeroes
Therefore 111 zeroes are added by multipliers and the original multiplicand that end in 0's.

2) Since any multiplier that ends with a 5 will follow one that ends with a 6, the first non-zero digit that the 5 will be multiplied to will be even, so that means all multipliers ending in 5 will add 1 more zero to the end. This is the series 995,985,...15,5 of which there are 100, thus adding another 100 zeroes.

So my guess (since I'm not 100% confident I've made the right assumptions) would be 211 zeroes at the end. Somehow this doesn't sound right but I can't see my error.

Now looking at cjg's solution, he seems to have gotten 249, which would suggest I'm way off, if he's right. Oh well, Prof Hinckley will explain all!

cjg said...

After the simple brute-force, I started working on an enumeration solution. So far I have the 111 for the multiples of 10.

The next step I did was to pair and value ending in 5 and 2 (that is, remove all those numbers from the list). That leaves approximately 211 as kimota. The next step would be to calculate all the pairs in this second set that generate numbers that end in 2 or more zeros. I haven't figured out any cases yet though.

Kimota94 aka Matt said...

Hey, when do we find out the right answer??

Anonymous said...

After Christmas, I guess