Proving the existence of a line that passes only through two points

Question

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?

Answer 1

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.

Claim: $A,B$ are the only points from $S$ on the line $(AB)$.

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.

Answer 2

IMHO your proof is wrong but not because of cyclic reasoning.

• Let $T=$ all triplets are collinear

• Let $A=$ all points are collinear

• You are saying: $T \implies A$. And since it is given $\lnot A$, you conclude $\lnot T$. ($\lnot$ is the NOT symbol.)

• Let $L =$ there exists a line through only two points, which you want to prove.

• Clearly $T \implies \lnot L$, or equivalently $L \implies \lnot T$. But you haven't explained what allows you to go $\lnot T \implies L$.

Indeed, logically speaking, $L$ is equivalent to $\exists A_i, A_j, \forall A_k, (A_i, A_j, A_k)$ is non-collinear. Meanwhile $\lnot T$ is $\exists A_i, A_j, A_k, (A_i, A_j, A_k)$ is non-collinear. So $L$ is a much stronger condition (logically) than $\lnot T$.

Now, obviously $L$ is true, so I'm just saying your proof is insufficient IMHO.

Answer 3

There is a simple proof without going into any deep knowledge of Mathematics. Just a little common sense and you are done. If $S$ be such a finite set then area enclosed by all points is finite. If that happens then we can construct an imaginary boundary around the points. Outside this field we draw a straight line , and surely none of the points of our set lie on this line. Since area enclosed by the points is trivial we can extend area and bring exactly two points from our parent set on the straight line. And then we have a set of points where there is a line passing through exactly $2$ points.