Let $n\ge 3$ be an integer. Let $S$ be the set of $n$ points in the plane such that they are not vertices of a convex polygon, and no three are collinear. Prove that there is a triangle with vertices among the given points such that there is exactly one point of $S$ in the interior of it.
This is a question I got from a friend. He challenged me with it. I lost it and now I am looking for a solution. Can someone help me?? Thanks.
The statement is vacuous if $n=3$: there is no such set $S$, because any set of 3 points is either collinear or is the vertex set of a triangle.
So it is safe to assume $n \ge 4$. The proof is by induction on the cardinality of $S$.
Let $H(S)$ be the convex hull of $S$, the unique convex polygon with the property that $S \subset H(S)$ and each vertex of $H(S)$ is in the set $S$ (the notation $H(S)$ is intended to incorporate not just the union of the vertices and the sides but also the interior). Notice that the only points of $S$ on the boundary of $H(S)$ are the vertices, for otherwise $S$ has three collinear points.
The basis of the induction is $n=4$. The polygon $H(S)$ has $\le 4$ vertices, but it cannot have exactly 4 vertices and it cannot have $\le 2$ vertices, so $H(S)$ is a triangle. There is exactly one point $p \in S$ which is contained in $H(S)$ but is not a vertex of $H(S)$, and $p$ is not on the boundary of $H(S)$, so we are done.
By induction, we may assume that $n>4$ and that the statement is true for all $i \le n-1$. The proof of the induction step has two cases, depending on whether the number of vertices of $H(S)$ is $=3$ or is $\ge 4$.
Case 1: $H(S)$ has $\ge 4$ vertices. Take $p,q \in S$ to be two vertices which are not endpoints of an edge. The segment $\overline{pq}$ cuts $H(S)$ into two convex polygons $Q_1 \cup Q_2$. No point of $S$ lies on the boundary of $Q_1$ or $Q_2$ other than the vertices of $H(S)$, and so there must be points of $S$ in the interior of either $Q_1$ or $Q_2$; up to switching subscripts, let's say that one is $Q_1$. Then we can apply the induction hypothesis to the set $Q_i \cap S$, whose cardinality is $\le n-1$, and we are done.
Case 2: $H(S)$ has exactly 3 vertices $p_1,p_2,p_3$. Pick a point $q \in S$ in the interior of $H(S)$. The points $p_1,p_2,p_3,q$ cut the triangle $H(S)$ into three triangles $T_1,T_2,T_3$ where $T_1$ has vertices $p_2,p_3,q$, etc. No point of $S$ other than $p_1,p_2,p_3,q$ lies on any side of any of $T_1,T_2,T_3$. Since the set $S' = S - \{p_1,p_2,p_3,q\}$ has $n-4 \ge 1$ points, it follows that one of the triangles $T_i$ contains a point of $S'$. We can then apply the induction hypothesis to the set $T_i \cap S$ whose cardinality is $\le n-1$ and we are done.