Problem:
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 , determine the largest integer such that no planar -gon splits into less than triangles.
Solution
Solution:
The required maximum is , the least integer greater than or equal to . To describe a planar -gon splitting into this many triangles, write , where is a positive integer and , and consider coplanar equilateral triangles , , where the are pairwise distinct, the 's of rank congruent to or modulo are all collinear, , in order, and the line separates from the remaining 's of rank congruent to modulo . The polygon settles the case ; removal of from the list settles the case ; and removal of and settles the case .
Next, we prove that no planar -gon splits into less than triangles. Alternatively, but equivalently, if a planar polygon splits into triangles, then its boundary has (combinatorial) length at most . Proceed by induction on . The base case is clear, so let .
The vertices of the triangles in the splitting may subdivide the boundary of the polygon, making it into a possibly combinatorially longer simple loop . Clearly, it is sufficient to prove that the length of does not exceed .
To this end, consider a triangle in the splitting whose boundary meets along at least one of its edges. Trace counterclockwise and let , in order, be the connected components of . Each is a path along with distinct end points, whose terminal point is joined to the starting point of by a (possibly constant) path along . Trace clockwise from the terminal point of to its starting point to obtain a path of positive length, and notice that is the boundary of a polygon split into triangles. By the induction hypothesis, the length of does not exceed , and since has positive length, the length of is at most . Consequently, the length of does not exceed .
Finally, we prove that the total length of the does not exceed . Begin by noticing that no has length greater than , at most one has length greater than , and at most three have length . If some has length , then the remaining are all of length at most , so the total length of the 's does not exceed . Otherwise, either some has length , in which case at most one other has length and the remaining all have length at most , or the all have length less than , in which case there are at most three of length and the remaining all have length at most ; in the former case, the total length of the 's does not exceed , and in the latter, the total length of the 's does not exceed . The conclusion follows.