Maths Olympiad Prep

Library / /13 of 16

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it JBMO

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 n3n \geq 3, determine the largest integer mm such that no planar nn-gon splits into less than mm triangles.

Solution

Solution:
The required maximum is n/3\lceil n / 3 \rceil, the least integer greater than or equal to n/3n / 3. To describe a planar nn-gon splitting into this many triangles, write n=3mrn = 3m - r, where mm is a positive integer and r=0,1,2r = 0, 1, 2, and consider mm coplanar equilateral triangles A3iA3i+1A3i+2A_{3i} A_{3i+1} A_{3i+2}, i=0,,m1i = 0, \ldots, m-1, where the AiA_{i} are pairwise distinct, the AA's of rank congruent to 00 or 22 modulo 33 are all collinear, A2,A3,A5,,A3m3,A3m1,A0A_{2}, A_{3}, A_{5}, \ldots, A_{3m-3}, A_{3m-1}, A_{0}, in order, and the line A0A2A_{0}A_{2} separates A1A_{1} from the remaining AA's of rank congruent to 11 modulo 33. The polygon A0A1A2A3A4A5A3m3A3m2A3m1A_{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=0r=0; removal of A3A_{3} from the list settles the case r=1r=1; and removal of A3A_{3} and A3m1A_{3m-1} settles the case r=2r=2.

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

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 α1,,αk\alpha_{1}, \ldots, \alpha_{k}, in order, be the connected components of Ωω\Omega - \omega. Each αi\alpha_{i} is a path along Ω\Omega with distinct end points, whose terminal point is joined to the starting point of αi+1\alpha_{i+1} by a (possibly constant) path βi\beta_{i} along ω\omega. Trace ω\omega clockwise from the terminal point of αi\alpha_{i} to its starting point to obtain a path αi\alpha_{i}' of positive length, and notice that αi+αi\alpha_{i} + \alpha_{i}' is the boundary of a polygon split into ti<tt_{i} < t triangles. By the induction hypothesis, the length of αi+αi\alpha_{i} + \alpha_{i}' does not exceed 3ti3 t_{i}, and since αi\alpha_{i}' has positive length, the length of αi\alpha_{i} is at most 3ti13 t_{i} - 1. Consequently, the length of Ωω\Omega - \omega does not exceed i=1k(3ti1)=3t3k\sum_{i=1}^{k} (3 t_{i} - 1) = 3t - 3 - k.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.