So I came across this question in a Math Olympiad Book:
Consider a finite set $S$ of points in a plane which are not all collinear. Show that there is a line in the plane which passes only through two points in $S$.
$$S = \{A_1, A_2,…,A_n\}$$
Since this was in the combinatorics section of the book, my first instinct was to construct a set (say $A$) which consists of increasing ordered triplets of $S$. Basically,
$$A=\{(A_1,A_2,A_3),(A_1,A_2,A_4),…\}$$
Furthermore, let us assume that every element $x$ of $A$ represents collinearity between those three points within $x$.
Now let us assume that there does exist a set $S$ such that no line passing through only two points exists. In that case $A$ would contain every single increasing ordered triplet using elements of $S$.
However we know that there is only one possible line passing between two points. Thus it means that if two triplets $(A_1,A_2,A_i)$ and $(A_1,A_2,A_j)$ are elements of $A$ then the line passing through $A_1$ and $A_2$ also passes through $A_i$ and $A_j$, which would imply that all four points are collinear. Similarly we know that $A$ contains all possible triplets of the form $(A_1,A_2,A_i)$ thus we can say that all the points are collinear.
This is a contradiction. Thus no such set can exist. $QED$.
However, I showed this proof to a friend and he told me that I was using cyclic reasoning and was incorrect. According to him I should prove that such a line exists rather than proving that no such set can exist. Is he right?
Best Answer
There is a beautiful proof that I can't resist to show here.
Consider the set $T := \{(A, B, C) \in S^3 \ \big| C \notin (AB)\}$. Since the points of $S$ are not all collinear, $T$ isn't empty. Now take $(A,B,C)\in T$ such that the distance $d\big(C,(AB)\big)$ from the point $C$ to the line $(AB)$ is minimal.
Suppose for contradiction that we have a third point from $S$, say $D$, on the line $(AB)$. Let $H$ be the orthogonal projection of $C$ on $(AB)$, we have $d\big(C,(AB)\big) = CH$. WLOG, we can assume that $D$ lies on the half line $[HB)$.
If $D$ is on the segment $[HB]$, then $d\big(D,(BC)\big)$ is strictly smaller than $CH$. If $D$ isn't on the segment $[HB]$, then $B$ is on the segment $[HD]$ hence $d\big(B,(DC)\big)$ is strictly smaller than $CH$. In both cases, we get a contradiction to the fact that $d\big(C,(AB)\big)$ is minimal.