
C4. A splitting of a planar polygon is a finite set of triangles whose interiors are pairwise disjoint, and whose union is the polygon in question. Given an integer $n \geq 3$, determine the largest integer $m$ such that no planar $n$-gon splits into less than $m$ triangles.


Solution. The required maximum is $\lceil n / 3\rceil$, the least integer greater than or equal to $n / 3$. To describe a planar $n$-gon splitting into this many triangles, write $n=3 m-r$, where $m$ is a positive integer and $r=0,1,2$, and consider $m$ coplanar equilateral triangles $A_{3 i} A_{3 i+1} A_{3 i+2}$, $i=0, \ldots, m-1$, where the $A_{i}$ are pairwise distinct, the $A$ 's of rank congruent to 0 or 2 modulo 3 are all collinear, $A_{2}, A_{3}, A_{5}, \ldots, A_{3 m-3}, A_{3 m-1}, A_{0}$, in order, and the line $A_{0} A_{2}$ separates $A_{1}$ from the remaining $A$ 's of rank congruent to 1 modulo 3 . The polygon $A_{0} A_{1} A_{2} A_{3} A_{4} A_{5} \ldots A_{3 m-3} A_{3 m-2} A_{3 m-1}$ settles the case $r=0$; removal of $A_{3}$ from the list settles the case $r=1$; and removal of $A_{3}$ and $A_{3 m-1}$ settles the case $r=2$.

Next, we prove that no planar $n$-gon splits into less than $n / 3$ triangles. Alternatively, but equivalently, if a planar polygon splits into $t$ triangles, then its boundary has (combinatorial) length at most $3 t$. Proceed by induction on $t$. The base case $t=1$ is clear, so let $t>1$.

The vertices of the triangles in the splitting may subdivide the boundary of the polygon, making it into a possibly combinatorially longer simple loop $\Omega$. Clearly, it is sufficient to prove that the length of $\Omega$ does not exceed $3 t$.

To this end, consider a triangle in the splitting whose boundary $\omega$ meets $\Omega$ along at least one of its edges. Trace $\Omega$ counterclockwise and let $\alpha_{1}, \ldots, \alpha_{k}$, in order, be the connected components of $\Omega-\omega$. Each $\alpha_{i}$ is a path along $\Omega$ with distinct end points, whose terminal point is joined to the starting point of $\alpha_{i+1}$ by a (possibly constant) path $\beta_{i}$ along $\omega$. Trace $\omega$ clockwise from the terminal point of $\alpha_{i}$ to its starting point to obtain a path $\alpha_{i}^{\prime}$ of positive length, and notice that $\alpha_{i}+\alpha_{i}^{\prime}$ is the boundary of a polygon split into $t_{i}<t$ triangles. By the induction hypothesis, the length of $\alpha_{i}+\alpha_{i}^{\prime}$ does not exceed $3 t_{i}$, and since $\alpha_{i}^{\prime}$ has positive length, the length of $\alpha_{i}$ is at most $3 t_{i}-1$. Consequently, the length of $\Omega-\omega$ does not exceed $\sum_{i=1}^{k}\left(3 t_{i}-1\right)=3 t-3-k$.

Finally, we prove that the total length of the $\beta_{i}$ does not exceed $k+3$. Begin by noticing that no $\beta_{i}$ has length greater than 4 , at most one has length greater than 2 , and at most three have length 2 . If some $\beta_{i}$ has length 4 , then the remaining $k-1$ are all of length at most 1 , so the total length of the $\beta$ 's does not exceed $4+(k-1)=k+3$. Otherwise, either some $\beta_{i}$ has length 3 , in which case at most one other has length 2 and the remaining $k-2$ all have length at most 1 , or the $\beta_{i}$ all have length less than 3 , in which case there are at most three of length 2 and the remaining $k-3$ all have length at most 1 ; in the former case, the total length of the $\beta$ 's does not exceed $3+2+(k-2)=k+3$, and in the latter, the total length of the $\beta$ 's does not exceed $3 \cdot 2+(k-3)=k+3$. The conclusion follows.

## Chapter 3

## Geometry
