Estonian Mathematical Olympiad

There has to be a point inside the convex hull of the set of marked points, otherwise any subset of points would form a convex polygon. Let us partition the convex hull into triangles by drawing a necessary amount of diagonals. As no three points are on the same line, the marked point inside the convex hull must be inside one of the triangles. The vertices of that triangle along with the marked point inside the triangle form a non-convex quadrilateral.

We show that it is possible to find 4 points among the vertices of the non-convex $n$-gon such that they form a non-convex quadrilateral. Let $A$, $B$, and $C$ be consecutive vertices of the $n$-gon such that the internal angle $\angle ABC>180^{\circ }$. Let $A^{\prime }$ and $C^{\prime }$ be points on the extensions of $AB$ and $BC$ over $B$. Then the closed broken line corresponding to the polygon has to go through the interior of $\angle A^{\prime }B{C}^{\prime }$. If this area contains a marked point, say $X$, then $ABCX$ is non-convex (Fig. 15).

Fig. 15

Alternatively, if there are no vertices of the $n$-gon within the interior of $\angle A^{\prime }B{C}^{\prime }$, then it has to be intersected by a side of the polygon, say $DE$, where $D$ is on the side of point $A$ and $E$ is on the side of point $C$ (Fig. 16). Let us show that then $DBCE$ is a non-convex quadrilateral. Indeed, the opposite sides $DB$ and $CE$ are non-intersecting as they are located in different regions of the plane bordered by the lines $A{A}^{\prime }$ and $C{C}^{\prime }$. The opposite sides $BC$ and $ED$ are also non-intersecting as they are sides of the original $n$-gon. In addition, $\angle DBC>180^{\circ }$.

Fig. 16

Let us prove by induction on $n$ that among the $n$ vertices of the $n$-gon it is possible to choose 4 vertices which form a non-convex quadrilateral. Trivially, the base case $n=4$ is true. Assume now that $n>4$ and that the statement is true for all non-convex polygons with less sides. A non-convex polygon has an interior angle greater than $180^{\circ }$ and also an interior angle smaller than $180^{\circ }$. Let's verify that it is not possible that every pair of angles one of which is greater than $180^{\circ }$ and the other one smaller than $180^{\circ }$ are neighbours to each other. Indeed, as each of the vertices has 2 neighbours, there could be at most 2 angles less than $180^{\circ }$ and at most 2 angles greater than $180^{\circ }$. But $n>4$, contradiction. Therefore, it is possible to find three consecutive vertices $A$, $B$, and $C$ and a vertex $E$ different from the former three, such that internal angle $\angle B<180^{\circ }$ and internal angle $\angle A^{\prime }>180^{\circ }$.

Fig. 17

If there is a vertex $X$ in the interior of triangle $ABC$, then $ABCX$ is non-convex. If there are no vertices in the interior of triangle $ABC$, then by removing point $B$ we get a $n-1$-gon which still has interior angle $\angle E>180^{\circ }$. Hence it has 4 vertices forming a non-convex quadrilateral by the induction hypothesis.