Prove that every convex polygon has at most one triangulation consisting entirely of acute triangles.
Problem
Source: Bulgaria EGMO TST 2017 Day 1 Problem 1
Tags: combinatorial geometry, triangulation, polygon, combinatorics
30.01.2024 09:59
Let $P$ be a convex polygon on $n\geq 3$ vertices. Recall that $P$ has sum of angles $180^{\circ}(n-2)$ (divide $P$ into $n-2$ disjoint triangles by drawing all diagonals through one of the vertices) and hence has at most three acute angles (else its sum of angles is less than $90^{\circ} \cdot 4 + 180^{\circ}(n-4) = 180^{\circ}(n-2)$, contradiction). Next, we prove by strong induction on $n\geq 4$ that $P$ has at least two triangles sharing at least two sides with $P$. For $n=4$ this is clear and for $n$ if we take an arbitrary edge $e$ in a triangulation, it divides $P$ either into a triangle with two common sides with $P$ and an $(n-1)$-gon, or into an $m$-gon and an $(n-m+2)$-gon for some $4 \leq m \leq n-2$, and by the induction hypothesis any of the latter has at least two triangles sharing two sides with it and hence at least one sharing two sides with $P$ (at most one triangle could have $e$ as a side, since the triangles are disjoint, by the definition of triangulation). Now we move on to the main problem. For $n=3$ the polygon $P$ is either acute or not and we are done. For $n\geq 4$ we proceed by induction, with $n=4$ being clear. For $n$ suppose that there are two triangulations $T_1$ and $T_2$, each containing only acute triangles. Let $p_1$ and $p_2$ be two triangles from $T_1$ which have two common sides with $P$ and let $q_1$ and $q_2$ be two triangles from $T_2$ which have two common sides with $P$. If all of $p_1$, $p_2$, $q_1$, $q_2$ are distinct, then we obtain that $P$ has at least four acute angles, contradiction! Hence without loss of generality $p_1$ and $q_1$ are the same triangle. But now, by removing the vertex $v$ which does not appear in any other triangle in $T_1$, the remaining part of $P$ has at most one acute triangulation by the induction hypothesis; adding back $v$ in the unique possible manner again gives at most one acute triangulation. This completes the proof.