Line through a Disc, Terminating Zeros

Date: 12/03/97 at 15:29:54
From: zoraida nodarse
Subject: Probability

A circular disc 1 millimeter in diameter contains 2 billion randomly 
situated points. Does there always exist a straight line passing 
through the disc that has exactly 1 billion of the points on each side 
of that line? Explain.

Date: 12/03/97 at 19:05:59
From: Doctor Daniel
Subject: Re: Probability

Hi there,

Let's consider a much smaller version of this problem, where there are 
only 10 points. (Probability rarely cares about the difference between 
10 and 2,000,000,000!) Is there definitely a line that separates the 
set so there are 5 on each side?

Suppose that there's not a vertical line which does this. That means 
that there is a line which has fewer than 5 points on either side of 
it. 

(Certainly, there's a line with more than 5 points on its right, and a 
line with more than 5 points on its left. As we move from left to 
right, either we find a line with 5 points on either side, or we find 
a line with fewer on both sides. If we find a line with 5 points on 
the left and 4 on the right, move left just a little bit, and there we 
go; 5 on each side!)

If there are fewer than 5 on either side of our line, then there are 
at least 2 points _on_ this line. But if we rotate the line a very 
small amount, then some number of points on the line will move to the 
left and some will move to the right, while no other points will move 
sides of the line at all. (That's because the number of points chosen 
is finite.) It's easy to convince yourself that some line will put the 
right number of points on either side.

This argument scales up to where there are 2,000,000,000 chosen 
points, not 10. Try to convince yourself!

Cheers,

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/03/97 at 19:57:35
From: Doctor Tom
Subject: Re: Probability

Sure.

First, draw lines passing though all pairs of points. Then find a 
point P that's not on any of those lines.

Draw an arbitrary line through that point, and consider the function
that is the difference between the number of points on the left and 
the number of points on the right. If that is zero for the line you've 
drawn, you're done - that line does the separation you want.

If not, rotate that line about the point P. As it rotates, it will 
pass over the 2 billion points one at a time. It cannot hit two at a 
time, since otherwise the point P would be on the line connecting 
those two points.

So as the line rotates, the function which is the difference between
the number of points on both sides changes by two each time one of the 
two billion points is crossed. After the line makes a complete half 
turn, the difference is reversed, so if the initial difference was 
120, for example, it will now be -120. Somewhere in the middle it had 
to pass zero. At that point, it split your points into two equal 
groups.

If you don't understand this, try it with, say, 8 dots on a sheet of 
paper. Find a point P that's off all the lines connecting pairs of 
8 points, and gradually rotate a ruler around so that it goes through 
the point P. Each time you cross a point, recalculate the difference 
between the number of points on each side and convince yourself that 
it has to hit zero within a half turn.

-Doctor Tom,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/04/97 at 23:37:29
From: zoraida nodarse
Subject: Probability

I have tried straight calculation by using a spreadsheet, but the 
number is too large. I tried to find a pattern.

Find the terminating zeros in the standard numeral 580!.

Date: 12/05/97 at 14:11:13
From: Doctor Daniel
Subject: Re: Probability

Hi there,

I'll give you a hint, and maybe you'll be able to figure it out from 
that.

There will be one zero at the end of n! for every time there's a 
factor of 10 in n!, right?  But 

   n! = n * (n-1) * (n-2) * ... * 5 * 4 * 3 * 2 * 1.  

So that means that if you look at every number between 1 and n and 
count the number of 2s and 5s which are in the factoring of them, then 
the minimum will be the number of 10s.

I'll give you an example:

14! = 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

That's 7*2*13 *2*2*3*11 * 5*2*3*3*2*2*2*7*3*2* 5 *2*2* 3 * 2, doing 
the prime factorizing. Count the number of 2's: there's 12, I think.  
Count the number of 5's: there's 2. Thus, 14! is 10*10* (a whole big 
thing that doesn't divide 10). Consequently, 14! ends in two zeros 
(and 14! = 87178291200, so this is right).

This should help you with your problem.

-Doctor Daniel,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 12/05/97 at 16:09:07
From: ZORAIDA NODARSE
Subject: Re: Probability

Thank you!