Line through a Disc, Terminating ZerosDate: 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! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/