Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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/
```
Associated Topics:
College Euclidean Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search