A convex $2000$-gon is given in the plane. Show that one can select $1998$ points in the plane such that every triangle with the vertices at vertices of the $2000$-gon contains exactly one of the selected points in its interior (excluding the boundary).
Problem
Source:
Tags: combinatorics, geometry, combinatorial geometry
25.07.2021 15:11
Label the vertices $1$ to $2000$. For a vertex $n$ place a point $P_n$ inside triangle $(1, 2000, n)$ and inside triangle $(n - 1, n, n + 1)$ for $2 \leq n \leq 1999$. This is possible since our polygon is convex. Observe that for a triangle to contain $P_n$ it must have vertex $n$ as $P_n$ lies inside triangle $(n - 1, n, n + 1)$. Now observe that for a triangle $T$ with vertices $(a, n, b)$ and $WLOG$ $a < b, T$ contains $P_n$ if and only if $a < n < b$. This follows since $P_n$ lies strictly within $(1, n, 2000)$. We will now prove that every possible triangle formed has exactly one of $P_k$ for $2 \leq k \leq 1999$ strictly inside it. Let the vertices of the triangle be $(x, y, z)$ and $WLOG$ $1 \leq x < y < z \leq 2000$. We have that $2 \leq y \leq 1999$ and since $x < y < z$ we have that this triangle strictly contains $P_y$. Note that our triangle can't contain any other point because if were to, this point would have to be $P_x$ or $P_z$ but since $x < y < z$ this is impossible. Thus, we have placed $1998$ points such that every triangle with the vertices at vertices of the $2000$-gon contains exactly one of the selected points in its interior.