A sleeping rabbit lies in the interior of a convex -gon. A hunter picks three vertices of the polygon and he lays a trap which covers the interior and the boundary of the triangular region determined by them. Determine the minimum number of times he needs to do this to guarantee that the rabbit will be trapped.
Solutions — 2
Solution 1
Let the -gon be . We claim that the answer is which is achieved by picking the triangles for .
For any , we claim that the entirety of is covered by triangles with one of their vertices at . To prove this, consider one point in the intersection of the triangle with each of for all . Observe that if the entire angle is not covered then at least one of these points is not in any triangle.
Thus, the sum of all angles covered by the triangles is at least , but each triangle covers only . Thus, we need at least triangles.
Solution 2
A set of triangles that cover the entire polygon is called a trapulation. For a trapulation , let be a minimal subset of vertices such that contains a triangulation of , where is the polygon with as vertices. Let be the set of triangles that have non-empty intersection with . For an edge of , we say that is uncovered if no triangle of contains (as a side).
Let be the minimum number of triangles in a trapulation and suppose . Let be a trapulation with triangles such that has minimum number of uncovered edges. Note that and .
Claim : Every edge of is covered.
Proof. Suppose an edge () is uncovered. Consider a point in the triangle formed by lines and . Note that . So, there must be a triangle containing . As lies on side of the line , is a vertex of . Let and be the other two vertices. If both, or both , then and are on different sides of the line which is not possible. So, w.l.o.g. let and . Now, if then contains . Otherwise, we can replace with the triangle and get another trapulation which preserves the covered edges and covers an additional uncovered edge. This contradicts the minimality of number of edges uncovered.
Now, if no triangle of contains at least two edges of , then which is a contradiction. So, there is a triangle that contains two edges, whose common end is say . In this case, contradicts the minimality of .