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/