An “elementary” problem

A few days ago, I was told the following problem:

Let E a finite set of points in the plane with the property that any line containing two points of E contains at least a third one. Show that E is included in a line.

I find this problem particularly interesting because the problem a priori reflects an affine property of the plane, however the only solution I know is very tricky and uses an additional structure of the plane…

Can you find the solution of this problem ?

This entry was posted in Mathematicians. Bookmark the permalink.

5 Responses to An “elementary” problem

  1. Juan Víquez says:

    I think if E is not contained in the line, then there is at least one point out of the line. Then, we can construct infinity lines using the existence of a third point in each of them. Therefore, knowing that each line is different (does not contain any of the previous points) then must be infinitely many points in E, which is a contradiction because E has finitely many points. Hence, E is contained in the line.

  2. Mingfeng Zhao says:

    Hi Fabrice Baudoin,
    When I took high school math, I did this problem by using a finite argument of points in $E$. Namely, if we assume $E$ is not contained in a line, since $E$ has finitely many points, consider the set of all possible of lines which are determined by any different two points in $E$ and one point outside the line, since everything is finite, then there is a line and a point such that the distance between the point $P$ and the line $\ell$ which is determined by points $A$ and $B$ in $E$ is smallest. Now we only need to show that there is no the third point in $E$ on $\ell$, then we get a contradiction with the assumption. If there were the third point $Q\in E$, by the smallest distance property, it is easy to see that the triangle $\Delta APB$ must be acute, otherwise it is not smallest. Since $Q\in\ell$, it is easy to see that one of triangles $\Delta QPA$, $\Delta APQ$, $QPB$ and $\Delta BPQ$ has smaller distance than $\Delta APB$, we get a contradiction. I think it is better to draw picture to describe what I am saying. Anyway, thanks a lot.

    • Hi Mingfeng, This is indeed the solution ! An appealing feature of this solution is that we need to introduce the distance function to a line which is a metric notion in order to solve an affine problem. I think that it illustrates how sometimes in mathematics the solution to a problem comes from additional structures. Similarly Perelman solved the Poincare conjecture, a problem in toplogy, by using Riemannian and differential geometry.

  3. Luis says:

    Hi Fabrice,
    A nice proof of this theorem is given by E. W. Dijkstra[1], although it again uses the notion of distance,
    it is constructive, it does not rely on taking the point with the smallest distance, and does not use a proof by contradiction.
    The proof is given by proving the termination of an algorithm that finds a line that goes through only two points in E, if E is not collinear. I, as a computer scientist, find the proof really appealing. The paper is also
    worth reading since it contains a detailed history of result.

    [1] http://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1016.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s