India — Team Selection Test

Let the $2024$-gon be $A_0A_1 \cdots A_{2023}$. We claim that the answer is $2022$ which is achieved by picking the triangles $\triangle A_0A_iA_{i+1}$ for $i = 1, 2, \dots, 2022$.

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

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

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

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

Proof. Suppose an edge $e = A_iA_j$ ($i < j$) is uncovered. Consider a point $P$ in the triangle formed by lines $A_iA_j, A_iA_{j+1}$ and $A_{i-1}A_{i+1}$. Note that $P \in \mathcal{P}_S$. So, there must be a triangle $T \in \mathcal{T}_S$ containing $P$. As $P$ lies on $A_i$ side of the line $A_{i-1}A_{i+1}$, $A_i$ is a vertex of $T$. Let $A_k$ and $A_\ell$ be the other two vertices. If both, $k, \ell \in \{i+1, \dots, j\}$ or both $k, \ell \in \{j+1, j+2, \dots, n, 1, \dots, i-1\}$, then $A_l$ and $P$ are on different sides of the line $A_iA_k$ which is not possible. So, w.l.o.g. let $k \in \{i+1, \dots, j\}$ and $\ell \in \{j+1, j+2, \dots, n, 1, \dots, i-1\}$. Now, if $k = j$ then $T$ contains $e$. Otherwise, we can replace $T$ with the triangle $A_iA_jA_\ell$ and get another trapulation $\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 $\mathcal{T}_S$ contains at least two edges of $\mathcal{P}_S$, then $|\mathcal{T}_S| \ge |S|$ which is a contradiction. So, there is a triangle $T$ that contains two edges, whose common end is say $A_i$. In this case, $S' = S - A_i$ contradicts the minimality of $S$. $\square$