Can a Straight Line Divide a Thousand Points Equally?

[DivineNathicana]

Please help!

“ALL steps must be shown:

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

N.B. You must prove this in general, not just for one specific case. I.e.: describe the process someone would take that given any thousand points, he or she could draw a line that divides them into two halves.

Show all steps used to obtain the answer.”

The only thing I got out of this problem was that I had to consider the slopes of the lines determined by each pair of points, and my teacher said that was true. I didn't get much further, though. I tried finding a mean point and slope, but that didn't work out too well. How would one even make sure that such a "mean line" would not hit any existing points?!

The only help I found online was calculus-level, and I'm a freshman (and no math whiz!). Please help!

Thank you,

Alisa

 

[hypermorphism]

Please help!

“ALL steps must be shown:

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

N.B. You must prove this in general, not just for one specific case. I.e.: describe the process someone would take that given any thousand points, he or she could draw a line that divides them into two halves.

Show all steps used to obtain the answer.”

The only thing I got out of this problem was that I had to consider the slopes of the lines determined by each pair of points, and my teacher said that was true. I didn't get much further, though. I tried finding a mean point and slope, but that didn't work out too well. How would one even make sure that such a "mean line" would not hit any existing points?!

The only help I found online was calculus-level, and I'm a freshman (and no math whiz!). Please help!

Thank you,

Alisa

You were on the right track with the slopes. If the number of points is 1000, then there are only 1000C2 = 500*999 possible slopes counting overlaps. Thus, choose a slope that is not present and draw a line through the thousand points with it. This line can only have hit at most one of the points, no matter where you draw it. Next, take the line and move it so that it covers no existing points (this is always possible because your points are isolated, and there is always another point between any two points) and is completely outside the set of points (since there are only a finite number of points, the set of points is bounded). Now translate it into the set of points. Since the line can only touch one point at a time, only one point may cross the line at a time. Thus translate the line until 500 points have crossed the line. This line divides your set in half.

 

[DivineNathicana]

Thank you for your help, hypermorphism. = )

I have a few questions: Why are there 1000C2 = 500*999 possible slopes, and what do you mean by overlaps? How do you know that the line can cross only one point at a time, and how do you know that if you moved it slightly, it wouldn't pass over more points than one? Also, when the line passes over the 500 points, wouldn't it still be sitting on one point? Is there a general formula for this? = /

- Alisa

 

[hypermorphism]

Thank you for your help, hypermorphism. = )

I have a few questions: Why are there 1000C2 = 500*999 possible slopes, and what do you mean by overlaps?

A line is uniquely determined by two points (point-slope formula). Assume the worst case scenario, that if you choose any two points out of the thousand points, they will have a slope different from every other pair of points. The method of counting the amount of subsets of size n (in this case 2) one can choose from a set with m elements is easily derived to be the combination number mCn (read "m choose n"). You can derive this yourself if you are familiar with factorials. We are counting overlaps because we have not included the fact that there may be some distinct pairs of points that have the same slope. We will be counting those same slopes as if they were different slopes.If you do not know anything about combinations, you can note that you don't need to know the exact number of slopes, only that since you have a finite number of points, the number of slopes defined by them is finite.

How do you know that the line can cross only one point at a time, and how do you know that if you moved it slightly, it wouldn't pass over more points than one?

We constructed the line so that it does not have the slope of any pair of points in the set. Thus it can only cross over at most one point, no matter where we put it. (Let the line touch one point. Assume that the line is touching two points in the set. Use the point-slope formula to derive the contradiction that the line does not have such a slope and thus the assumption that the line passes through the second point is wrong.)

Also, when the line passes over the 500 points, wouldn't it still be sitting on one point?

We are translating the line parallel to itself. There is always an open set the line can pass through between any two points in the real plane (Note that the distance between two distinct real points is never 0).

Is there a general formula for this? = /

Luckily, the question didn't ask for a formula, just a proof that it is possible with a hint to describe how it is possible. The algorithm is better implemented by a computer program than trying to write such an ugly long formula (if you take the time to extract it from the description) on paper.

 

[DivineNathicana]

Oh, I more or less get it now, thank you! One thing, though: I understand why nCr= 499500, and that 500*999 is also 499500, but I don't understand where you got 500 and 999 from. Also, can you please tell me the formula and its name just for reference?

So to be able to actually solve this one would need to actually compute all of the possible slopes between any two points out of the thousand?! At least I wasn't asked to show it graphically heh...

Also, am I understanding correctly that we are simply sliding the line to make sure it does not hit any points rather than rotating it? Rotating it would change the slope.

One more thing: This means that there can pretty much be an infinite number of solutions since Infinity-499500 still equals Infinity, right?

Much thanks,

Alisa

 

[DivineNathicana]

Also, instead of letting points pass over the line one by one, wouldn't it make sense to first find the mean point (nx/n,ny/n) and draw a line through that? And one more thing: there are an infinite number of slopes that won't be present in the 1000 points, even if there ARE a possible 499500 ones - how do we know which to choose?

And are you saying that in order to solve this problem, one would have to calculate 499500 slopes? That's a bit unrealistic.

 

[DivineNathicana]

Also, why can't the line have one of those 499500 slopes? If it did, it wouldn't necessarily have to cross any points: the lines with a slope equal to its could have a different y-intercep, and would thus just be parallel, not coinciding.