Mathematical Reflections 2014, Issue 4 - Problem J309

Problem:

Let $n$ be an integer greater than $3$ and let $S$ be a set of $n$ points in the plane that are not the vertices of a convex polygon and such that no three are collinear. Prove that there is a triangle with the vertices among these points having exactly one other point from $S$ in its interior.

Proposed by Ivan Borsenco.

Solution:

We use the following theorem.

Carathéodory's Theorem.
If $\mathbf{x} \in \mathbb{R}^d$ lies in the convex hull of a set $S$, there is a subset $S'$ of $S$ consisting of $d+1$ or fewer points such that $\mathbf{x}$ lies in the convex hull of $S'$.

Let $\mathbf{x} \in S$ such that $\mathbf{x}$ lies in the interior of the convex hull of $S$. Hence, by Caratheodory's Theorem ($d=2$), there is a subset $S'$ of $S$ having at most $3$ points such that $\mathbf{x}$ lies in the convex hull of $S'$. Since the points are not collinear, then $|S'| \neq 2$ and since $\mathbf{x}$ lies in the interior of the convex hull of $S$, then $|S'| \neq 1$. So, $|S'|=3$ and there exists a triangle $T$ whose vertices are in $S$ which contains $\mathbf{x}$. If $\mathbf{x}$ is the unique point of $S$ in $T$, we are done. If there is another point $\mathbf{y} \neq \mathbf{x}$ of $S$ in $T$, joining $\mathbf{x}$ with the three points in $S'$ we have that $\mathbf{y}$ lies in the interior of one among these triangles. Proceeding in this way and using the fact that $S$ has finitely many points, then there exists a triangle whose vertices are in $S$ which has exactly one point of $S$ in its interior.