Line through Two Million Points
Date: 11/11/96 at 14:47:09 From: Kathryn Redfern Subject: Two million points Dr. Math, I am a student at Western Washington University in Jerry Johnson's Non-Euclidean Geometry class. We had a Problem of the Week last week that only three students were able to solve. Jerry asked the class to talk about the problem with anyone we could to arrive at a solution. Do you know how to solve the following problem? Two million points are randomly scattered in a circle. Must there always be a straight line that passes through the circle and has a million points on each side? Explain your answer/reasoning. Thank you, Kathy Redfern
Date: 01/04/97 at 15:26:50 From: Doctor Wilkinson Subject: Re: Two million points I would guess that you have thought about starting with a line just touching the circle at some point and moving it (keeping the same orientation) across the interior of the circle. As it moves, the points scattered through the interior of the circle which started on one side will pass to the other. Initially all the points are on one side and if you move the line all the way across they will all end up on the other side. You would think that at some point in between, exactly half would be on one side and half on the other. The problem, as no doubt you also noticed, is that you might find some number of points right on the line. For example, you could pass from having 999,999 points on one side and 1,000,001 points on the other side to having 999,999 points on one side, 999,999 points on the other, and two points on the line, to having 1,000,001 points on one side and 999,999 points on the other, without ever having 1,000,000 on each side. Right? But this is not as bad a problem as it seems, because there are only a finite (though large) number of pairs of points in the set, and therefore only a finite number of lines containing two or more points of the set. If we pick a line with a slope different from the slope of any of those lines, then the problem does not occur. Now that we have an intuitive picture of how it works, let's try to make it into a real proof. For every pair of points (x1, y1) and (x2, y2) there is at most one real number m such that both points lie on some line y = mx + b. (This is a simple matter of algebra). So we can find a real number m (namely any other m) such that the numbers of the form y - m*x, where (x, y) is a point in the given set, are all distinct. So just arrange these numbers in increasing order, and choose b to lie between the 1,000,000th and the 1,000,001th of these. Then the line y = m*x + b has the desired property. -Doctor Wilkinson, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.