Prove that there exists a set $ S$ of $ n - 2$ points inside a convex polygon $ P$ with $ n$ sides, such that any triangle determined by $3$ vertices of $ P$ contains exactly one point from $ S$ inside or on the boundaries.
Problem
Source: Romanian TST 1 2008, Problem 4
Tags: analytic geometry, induction, combinatorics proposed, combinatorics
02.05.2008 18:50
Let's try to construct this set of $ n-2$ points. Let our convex polygon $ P$ be $ A_1A_2\ldots A_{n-3}A_{n-2}YX$. Let $ \{E\}=A_1Y\cap A_2X$. Pick a point $ M$ inside triangle $ XEY$. It is easy to see that $ M\in\text{Int}(\triangle XA_iY)$ for all $ i$. Let now $ U=\displaystyle\cup_{i=1}^n\text{Int}(\triangle XA_iY)$. Define now the points $ T_i=XA_{i+1}\cap YA_i$, for $ i=1,2,\ldots,n-3$. Then $ U$ is the concave polygon $ XA_1T_1A_2T_2\ldots A_{n-1}T_{n-1}A_nY$ (a drawing would really help here). Clearly none of the remaining points of $ S$ can be located inside $ U$. Then these points must lie in the region $ P\setminus U$ which is the union of $ n-3$ disjoint triangles: $ P\setminus U=\displaystyle\cup_{i=1}^{n-3}\text{Int}\triangle{A_iT_iA_{i+1}}$. Consider now the triangles $ Y_i=XA_iA_{i+1}$ for $ i=1,2,\ldots,n-3$. None of them contains $ M$. In the end each of them must contain exactly one point from $ S$. Since $ Y_i\setminus U=\triangle A_iT_iA_{i+1}$, we obtain that each triangle $ Y_i\setminus U$ will contain exactly one point, giving a total of $ n-2$ points. Let's proceed with the construction of $ S$. Take any point in the region $ P\setminus U$ and consider all the triangles containing it. Let $ U'$ be the union of $ U$ and all these triangles. Then repeat this process until $ U'=P$. Let's see that this process is correct. Consider the number of triangles who have no point of $ S$ inside. At each step this number obviously decreases (because the chosen point lies outside $ U$, hence any triangle containing it is not included yet in $ U$). At some point this number will be $ 0$ (that is $ U=P$). Assume that at this point $ S$ has $ k$ points. According to the above observation $ k\ge 1+(n-3)=n-2$ and since none of the initial triangles $ A_iT_iA_{i+1}$ may contain more than $ 1$ point, we obtain $ k=n-2$. Moreover since in the end the number of triangles not containing any point of $ S$ is $ 0$, any triangle has at least one point from $ S$ inside. Also, by the construction of $ U'$ from $ U$ we ensure that no triangle will contain more than $ 1$ point of $ S$.
03.05.2008 22:02
Old problem, no? Choose a coordinate system such that no two of the given $ n$ points have the same $ x$-coordinate. Let $ P_1,\cdots, P_n$ be the vertices of the $ n$-gon in the increasing order of their $ x$-coordinates. Now, since there is a finite number of points, there is a finite number of diagonals. Let $ d>0$ be the minimal distance between a vertex of the $ n$-gon and a diagonal (which has not the point as its endpoint). Now, for each vertex $ M_i$ with $ 1<i<n$, let's consider the point $ P_i$ which has the same $ x$-coordinate, is an interior point of the polygon and such that $ M_iP_i = \frac d 2$. It's a easy to see that the set of these $ n-2$ points $ P_i$ satisfies the desired condition. Pierre.
08.05.2008 14:26
A posted a "solution" yesterday which was a bit incomplete, Consider the triangles $ \Delta_i = A_1 A_i A_n$, where $ i \in \overline{1,n - 1}$. Take the points $ X_i \in \Delta_i$ very close to $ A_i$. How close? Well close enough, so that the triangle $ A_i A_j A_k$ with $ i \leq j \leq k$ has only the point $ X_j$ inside it. Again, this seems to work (for strictly convex polygons anyway). [I originally posted some sort of an induction in which we added a point near to a vertex and inside a triangle at every step, but somehow I failed to see that all of those triangles had the same "base", which I now named $ A_1 A_n$.] If the polygon isn't strictly convex, then I don't think we can find points as in the problem (take for example a pentagon with three collinear vertices).
12.09.2012 14:45
Let $0, 1,....,n-1$ be a cyclical indexing for the vertices of $P$, and $Q$ a fixed point interior to the side $[n - 1,0]$. For each $i$ in ${1,....., n - 2}$, consider ne point each $i$' interior to the segment intercepted by the triangle $[i - 1, i, i + 1]$ on the segment $[i, Q]$. The set of the points $i$' satisfies the stated requirement, since from the convexity of $P$, for any $i, j, k$ distinct vertices of P, one only of the segments $[i,Q], [j,Q], [k,Q]$ contains a point interior to the triangle $[I,j,k]$,So done.