A Thousand Points

Question

A 1000 points are graphed in the co-ordinate plane. Explain why it is possible to draw a straight line in the plane so that half the points on one side of the line and half are on the other.

This question was taken from Precalculus by Stewart,Watson.

Answer 1

Consider the $xOy$ plane with $1000$ points randomly distributed. We want a line $y = mx+b$ such that above it we have $500$ points and under it we have the other $500$ points.

We start by choosing the slop of our line. We will choose the slop of our line in a such a way that this line is not parallel to any other line that passes through two of those $1000$ points.

Hence, this line will not intersect any of those $1000$ points or it will only intersect one of those points at a time.

Then, we choose a $b$ such that all the $1000$ points are under the line. By decreasing the value of $b$, the line will pass through the points one at time. In no moment, we will have two of those points belonging to this line at the same time.

So, by decreasing the line until it passes through $500$ points, we have that there are already $500$ points above it. Now, we have to make sure that the other $500$ are under it.

It may happen the case when we have $499$ points under it and the other one point belonging to the line. But we can surpass this by getting a difference $b$ such that this not happens.

This works because of the fact that between any two real numbers, there are a real number; something that I am not sure if you know, but by intuition you can see that is true.

Answer 2

Start with 2 points A and B, draw AB's perpendicular line k to separate A and B.

Next, add 2 points C and D. There are 3 different scenarios:

1. C , D on different sides of k. No action needed.

2. Both C,D or one of them is on line k (assume C on line k, D either on k below C or to the left of k).

Find a point Y slightly lower than C, rotate k around Y CCW by an infinitely small angle $\delta \theta$ to move C to the right side of k(since the size of a point is 0), k separates 4 points evenly.

3. C, D on the same side of k (assuming left side).

Among all points on the left side, find the point set {$X_i$} that is closest to line k.

Move k parallelly to overlap with {$X_i$}.

Let $X_0$ be the top of all the points (for example C). Y is a point slightly lower than $X_0$ on k.

Rotate k around Y CCW by an infinitely small angle $\delta \theta$ to move C to the right side of k, then k separates all points evenly.

Since $\delta \theta$ is an infinitely small angle, after each rotation adjustment,k is almost still perpendicular to AB (given the adjustment time is not infinity).

Repeat these steps by adding 2x points once a time and adjust k's location and orientation accordingly till we reach 1000 points.

Answer 3

$1000$ points define a finite number of directions. Choose a line that has a different direction (so that it cannot contain two points).

Then by translating the line, you can leave any number of points on a side. On the picture, the green line has a different direction than the $15$ pairs of points (check the directions rose).

Answer 4

So my first thought is draw any line. If more points are on one side than the other than just slide the line parallel up or down to cross more points to increase the number of points on one side and less the number of points on the other.

The problem is we don't know that if we shove the line it won't intersect two or more points at a time or that as we nudge it it won't "immediately" intersect more.

But as there are only finitely many points and uncountably many slopes a line can take we can easily construct a line so that it intersects no points and as we slide it.... it can still intersect two points at a time.

Well, there are $1000$ points. SO there are ${1000\choose 2} = \frac {1000\times 1001}2 = 500500$ pairs of points so we can find a line whose slope isn't equal to any of the lines formed by connecting two points. Thus if we slide this line parrallelly, it will never intersect two points. So we can just slide it until it crosses on point at a time until we get $500$ above and $500$ below.

But we still have the issue of how can we know that we can cross one point and not "immediately" hit another.

Well, when the line hits a single point there are $999$ other points not on the line. $999$ is a finite number so if we compare all the points and their distance to the line. There must be some minimum positive value. And when we slide off the point at less than that minimum value, we will slide of our current point an not "immediately* hit another.

So that's it. We make a line with a slope that is no parallel to any pair of points. We count how many points are above and below it. We slide it in the direction to make it more balanced. Because the line is not parallel to any pair as we slide it it will intersect and pass individual points one at a time. And we can slide it until we adjust the numbers perfectly.