Maths Olympiad Prep

Library / /82 of 91

Geometry Difficulty 7.8 National Olympiad, round 2 Prove it India

A sleeping rabbit lies in the interior of a convex 20242024-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 20242024-gon be A0A1A2023A_0A_1 \cdots A_{2023}. We claim that the answer is 20222022 which is achieved by picking the triangles A0AiAi+1\triangle A_0A_iA_{i+1} for i=1,2,,2022i = 1, 2, \dots, 2022.

For any 0i20230 \le i \le 2023, we claim that the entirety of AiAi+1Ai+2\angle A_iA_{i+1}A_{i+2} is covered by triangles with one of their vertices at Ai+1A_{i+1}. To prove this, consider one point in the intersection of the triangle AiAi+1Ai+2A_iA_{i+1}A_{i+2} with each of Ai+1AjAj+1A_{i+1}A_jA_{j+1} for all ji,i1j \ne i, i-1. 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 (2022)180(2022) \cdot 180^\circ, but each triangle covers only 180180^\circ. Thus, we need at least 20222022 triangles. \square

Solution 2

A set of triangles that cover the entire polygon P\mathcal{P} is called a trapulation. For a trapulation T\mathcal{T}, let S{A1,A2,,An}S \subset \{A_1, A_2, \dots, A_n\} be a minimal subset of vertices such that T\mathcal{T} contains a triangulation of PPS\mathcal{P} - \mathcal{P}_S, where PS\mathcal{P}_S is the polygon with SS as vertices. Let TST\mathcal{T}_S \subset \mathcal{T} be the set of triangles that have non-empty intersection with PS\mathcal{P}_S. For an edge ee of PS\mathcal{P}_S, we say that ee is uncovered if no triangle of TS\mathcal{T}_S contains ee (as a side).

Let tt be the minimum number of triangles in a trapulation and suppose t<n2t < n-2. Let T\mathcal{T} be a trapulation with tt triangles such that T\mathcal{T} has minimum number of uncovered edges. Note that TS<S2|\mathcal{T}_S| < |S| - 2 and S4|S| \ge 4.

Claim : Every edge of PS\mathcal{P}_S is covered.

Proof. Suppose an edge e=AiAje = A_iA_j (i<ji < j) is uncovered. Consider a point PP in the triangle formed by lines AiAj,AiAj+1A_iA_j, A_iA_{j+1} and Ai1Ai+1A_{i-1}A_{i+1}. Note that PPSP \in \mathcal{P}_S. So, there must be a triangle TTST \in \mathcal{T}_S containing PP. As PP lies on AiA_i side of the line Ai1Ai+1A_{i-1}A_{i+1}, AiA_i is a vertex of TT. Let AkA_k and AA_\ell be the other two vertices. If both, k,{i+1,,j}k, \ell \in \{i+1, \dots, j\} or both k,{j+1,j+2,,n,1,,i1}k, \ell \in \{j+1, j+2, \dots, n, 1, \dots, i-1\}, then AlA_l and PP are on different sides of the line AiAkA_iA_k which is not possible. So, w.l.o.g. let k{i+1,,j}k \in \{i+1, \dots, j\} and {j+1,j+2,,n,1,,i1}\ell \in \{j+1, j+2, \dots, n, 1, \dots, i-1\}. Now, if k=jk = j then TT contains ee. Otherwise, we can replace TT with the triangle AiAjAA_iA_jA_\ell and get another trapulation T\mathcal{T}' which preserves the covered edges and covers an additional uncovered edge. This contradicts the minimality of number of edges uncovered. \square

Now, if no triangle of TS\mathcal{T}_S contains at least two edges of PS\mathcal{P}_S, then TSS|\mathcal{T}_S| \ge |S| which is a contradiction. So, there is a triangle TT that contains two edges, whose common end is say AiA_i. In this case, S=SAiS' = S - A_i contradicts the minimality of SS. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.