There are N (here N is a finite number) points distributed in the plane (plain surface).
Configurations with ALL N points arranged along a single straight line are disregarded.
Prove that there exists at least one straight line
going through ONLY TWO points from the given generic set of points.
milkyway:
I think your answer is incomplete. Unfortunately, I don't have my own proof, but let me criticize yours.
Sorry.:-)
What is definitely proven by induction in your post is that you are able to construct an acceptable set of N points. However, in my view, your reasoning does not prove the statement for a given set.
1. From the very beginning, you have N points. How can one realize the induction scheme in this case? Perhaps, you mean that you can temporarily erase N-3 points (keeping in mind their positions) and start with 3 points forming a triangle, or "3 couples" in your terms. Then you restore the erased points one by one at their positions. I believe this should be explained in your proof.
2. Note that if you start with 3 aligned points, by "restoring" the 4th point, you can generate an allowed set of N+1 points out of the prohibited set of N points. This is missing in your proof, where you deal only with allowed N-sets.
But this is not the most serious flaw there.
3. You write: "now, this way there always are the old two couples, plus two new couples (new point-non aligned point of each of such two couples). So going from N to N+1, the number of acceptable couples is always >=3."
I disagree with this statement.
Indeed, imagine that the three couples, which work at the stage N, form a triangle. Aligning the newly "restored" point with one side of the triangle, you kill one working couple. Still you have the two remaining old couples and get a possibly working new couple (new point - non aligned point of the triangle). However, it is not at all guaranteed that there is no other point lying on the line going through this new possibly working couple. If such point exists, the number of working couples in this case gets reduced from 3 to 2 when going from N to N+1. At the next step, this way I will reduce the number of working couples from 2 to 1 and so on.
The transition from N to N+1 is therefore not justified.
4. A general question. For N=infinity the statement is false for points located at nodes of a regular
(say, square) lattice. Doesn't it contradict to the very idea of proving this statement by induction?
- - - - - - - - - - - - - - -
Here is my proof.
Given a set of N points, the number of all possible couples is M=N(N-1)/2.
For each couple draw a straight line going through it. We get M lines.
Let us assume that the statement we are going to prove is false: i.e., none of those M lines goes through ONLY TWO points.
Then, of course, each of those M lines coincides with at least the two other lines, so the actual number of distinguishable lines K < M.
We have N points and K different lines.
Each of the NK pairs (point + line) is characterised by a distance S(n,k) between the point n and the line k.
This distance S(n,k) is defined as a length of a segment perpendicular to the line k with one of the ends lying on the line k and the other end coinciding with the point n.
Let us list all the NK distances S(n,k). Since NK is a finite integer number, one can find the shortest value (or several equal shortest values) of S(n,k).
Take a closer look at the point P and the line L with the shortest S(n=P,k=L).
By assumption, there are at least three points (L1,L2, and L3) lying on the line L. Therefore, at least two of these three points (say, L1 and L2) can be found to the one side (say, to the right) of the point A where the perpendicular to the line L starting at the point P hits the line L. The case when one of the three points (say, L1) coincides with the point A is treated in exactly the same way.
Now we have a triangle (P-L1-L2), with two vertices L1 and L2 lying on the line L to the right of A in the order A,L1,L2 from left to right.
Since L1 lies to the right of A (or coincides with A), the angle between P-L1 and L1-L2 is greater than (or equal to) pi/2.