Junior Balkan Mathematics Olympiad

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 = 3m - r$, where $m$ is a positive integer and $r = 0, 1, 2$, and consider $m$ coplanar equilateral triangles $A_{3i} A_{3i+1} A_{3i+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_{3m-3}, A_{3m-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_{3m-3} A_{3m-2} A_{3m-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_{3m-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 $3t$. 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 $3t$.

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}'$ of positive length, and notice that $\alpha_{i} + \alpha_{i}'$ is the boundary of a polygon split into $t_{i} < t$ triangles. By the induction hypothesis, the length of $\alpha_{i} + \alpha_{i}'$ does not exceed $3 t_{i}$, and since $\alpha_{i}'$ 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} (3 t_{i} - 1) = 3t - 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.