Prove Colinearity of Set of n Points

[didi]

Hi,
Can you tell me how to prove the following?

Given a set of n distinct points in the plane such that for any two points in the set there is a third point in the set that is colinear with them (i.e., lies on the same line with them), prove that all the n in the set are colinear (i.e., lie on the same line).
Thank you
didi

 

[arildno]

It seems you can use induction here:
1) Prove that the proposition holds for n=3
2) Try to do the induction step on your own

 

[PhilG]

2) Try to do the induction step on your own

Suppose the induction hypothesis is that the theorem holds for n = k-1 points, and you want to show that implies it holds for n = k points. In a set of k points, how do you know that there is a subset of k-1 points that satisfies the condition in the statement of the problem? What if that k-th point is the one that holds everything together?

 

[snoble]

I've been thinking about this problem and I don't see how you do it with induction. arildno can you explain how the inductive step works because I can't seem to think my way through it.

The proof that I can think goes like this
Say for contradiction you have a point set P that satisfies above but is not a line. Take L to be the set of lines that contain 2 or more points from P (in fact they all contain 3 points). Note that both L and P are finite. Also you can measure distance between a point and a line as the perpendicular distance.

So there are a also a finite amount of distances between points and lines and at least one distance is greater than zero (for every line you have at least one point such that the point is not on the line). Because there are only finitely many there is a minimum non-zero distance. Also I can describe a line by 2 points on that line (although this description is not unique it doesn't have to be). Take point b and line (p,q) such that the point line distance is the minimum. Take r to be the 3rd point on line (p,q). Take c to be the perpendicular projection of point b onto (p,q). Also we can assume the order of the points is p then q then r on line (p,q) (this would be a lot easier with a diagram). Well now either q=c, or q is to the right of c or q is to the left of c.

I will show one case since the rest is the same.
Assume q and r on the same side of c (say right of c). Now call the perp projection of q onto (b,r) d. Now you have two similar triangles (b,c,r) and (q,d,r). But qr is shorter than rc which is shorter than br (since br is the hypotenuse) so qd is shorter than bc. But that means q is closer to line (b,r) than b is to (q,r). But that's a contradiction since we chose distance between b and (q,r) to be of minimum distance.

Again arildno I would love to see the inductive method of solving this.
Thanks, Steven

 

[PhilG]

Brilliant proof, snoble. Here's a diagram to go with it

 

[didi]

colinear points

Thank you all of you for your help

Didi