Problem
ALG-B1-M05-P019 Diagonals Step by Step
In a convex \(n\)-gon, diagonals are drawn one by one so that each new diagonal intersects at most one previously drawn diagonal inside the polygon. Prove that at most \(2n-6\) diagonals can be drawn, and give a construction attaining this number.
For the upper bound, consider the last diagonal and cut the polygon into two parts.
Construction: draw \(A_2A_4,A_3A_5,\ldots,A_{n-2}A_n\), then \(A_1A_3,A_1A_4,\ldots,A_1A_{n-1}\). There are \((n-3)+(n-3)=2n-6\) diagonals, and the order can be chosen so that each new one intersects at most one old one.
For the upper bound, use induction on \(n\). The triangle is clear. Let the last diagonal be \(A_1A_k\). It intersects at most one previous diagonal \(d\). All other diagonals lie inside one of the two polygons \(A_1A_2\ldots A_k\) or \(A_kA_{k+1}\ldots A_nA_1\). By induction, their number is at most \((2k-6)+(2(n+2-k)-6)=2n-8\). Adding the last diagonal and possibly \(d\), we get at most \(2n-6\).
The final olympiad idea is rewritten as a general extremal sequence of steps.