I select points and draw lines in the plane according to the following rule : I start with an initial set of five distinct points, no three of which are on the same line, and at each step I either draw a new line passing through two distinct already selected points, or select an intersection point between two already drawn lines.

How to prove (or find a counterexample) that the process can be continued indefinitely, that there always will be new points to be selected or new lines to be drawn ?

Note that the process may stop when we start with only four points.

  • $\begingroup$ Show us that the process always stops when we start with only four points. $\endgroup$ – Christian Blatter Jan 20 '18 at 19:32
  • $\begingroup$ @ChristianBlatter The process may stop if we start with four points, namely if they are the vertices of a parallelogram $\endgroup$ – Hagen von Eitzen Jan 20 '18 at 19:37
  • $\begingroup$ @HagenvonEitzen Corrected, thanks $\endgroup$ – Ewan Delanoy Jan 20 '18 at 20:48

Suppose the process stops after finitely many steps, producing only a finite set $\mathcal P$ of points (and also only finitely many lines). Let $P_1,\ldots, P_n\in\mathcal P$ be the vertices of the convex hull $\mathcal P$.

If $n>4$, then $P_3P_4$ and $P_4P_5$ cannot both be parallel to $P_1P_2$, hence one of them intersects $P_1P_2$ in a point $Q\in\mathcal P$. But $Q$ is outside $P_1\cdots P_n$, contradiction. enter image description here

If $n=4$, we similarly conclude that $P_1P_2\|P_3P_4$ and $P_2P_3\|P_4P_1$, i.e., the 4-gon is a parallelogram. Let $O$ be the intersection of $P_1P_3$ and $P_2P_4$. As $P_1,P_2,P_3,P_4,O$ cannot be our original five points, there exists $Q\in\mathcal P\setminus\{P_1,P_2,P_3,P_4,O\}$. Assume $Q$ is an interior point of the 4-gon. Then one of the four lines $P_iQ$ intersects the boundary of our 4-gon in a non-vertex $S\in \mathcal P$. On the other hand, if $Q$ is not an interior point, it is itself a non-vertex boundary point, i.e., we can take $S=Q$. Wlog. $S$ is on edge $P_1P_2$ and is strictly between $P_1$ and $P_2$. Then the lines $P_3S$ and $P_4P_1$ intersect outside the 4-gon, contradiction.

enter image description here

Finally, consider the case $n=3$. Assume that the line $P_1P_2$ contains no points $\in\mathcal P$ except $P_1,P_2$ themselves. Then all points of $\mathcal P$ are on the triangle boundary as an interior point $Q\in\mathcal P$ would lead to $P_3Q\cap P_1P_2$. If $Q_1\in\mathcal P$ is a boundary point between $P_2$ and $P_3$ and $Q_2\in\mathcal P$ is a boundary point between $P_1$ and $P_3$, then $P_1Q_1\cap P_2Q_2$ is an interior point, which we have just shown is impossible. Hence all points of $\mathcal P\setminus\{P_1,P_2\}$ are on one of the edges $P_2P_3$ or they are all on $P_1P_3$. In particular, four of the original five points are collinear, contradiction. We conclude that $P_1P_2$ contains points $\in \mathcal P$ apart from $P_1$ and $P_2$. The same argument aplpies to the other edges, hence we find $Q_3\in\mathcal P$ between $P_1$ and $P_2$, $Q_1\in\mathcal P$ between $P_2$ and $P_3$, $Q_2\in\mathcal P$ between $P_3$ and $P_1$. Let $S=P_3Q_3\cap Q_1Q_2$ and $T=P_1S\cap P_2P_3$. Then $T$ is none of $Q_1,P_2,P_3$, hence one of the lines $TQ_2$, $Q_1Q_2$ is not parallel to $P_1P_2$ and leads to an intersection point outside the triangle, contradiction. enter image description here

Some remarks about the case of four starting points

If the four original points are the vertices of a parallelogram, it is indeed the case that we can find the edges, the diagonals, and the centre of the parallelogram, but then the process stops enter image description here

But if the convex hull of the four original points is a triangle (red dots in the image), we can find several points, among which we can find five points (marked with green circles) such that no three of them are collinear. By the analysis above, the process won't stop once we have these. enter image description here

Remains the case that the convex hull of the four points is a quadrangle, but not a parallelogram. Then from two non-parallel opposing edges, we can construct four points (again, marked with green circles) such that no htree are collinear and their convex hull is a triangle. According to the preceding paragraph, the process won't stop.

enter image description here

  • $\begingroup$ Very nice ! To summarize the proof in a sentence : the set must be infinite because its convex boundary must keep on extending. $\endgroup$ – Ewan Delanoy Jan 20 '18 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.