Maths Olympiad Prep

Library / /14 of 39

Geometry Difficulty 6.1 National Olympiad Prove it Croatia

Let n3n \ge 3 be a positive integer. Some diagonals are drawn in a convex nn-gon. We say that a drawn diagonal is good if it intersects another drawn diagonal in its interior. Determine the maximal possible number of good diagonals.

Solution

Let M(n)M(n) be the maximal possible number of good diagonals in a convex nn-gon.
We will show that M(n)=n2M(n) = n - 2 if nn is even and M(n)=n3M(n) = n - 3 if nn is odd. For any nn, we can draw all n3n - 3 diagonals from one vertex AA and one more diagonal joining two vertices adjacent to AA if n>3n > 3. We show by mathematical induction that M(n)n2M(n) \ge n - 2 if nn is even. For n=4n = 4 the claim is true as both diagonals in a convex quadrilateral are good. Let us assume that the claim is true for n2n - 2 and consider a convex nn-gon A1A2...AnA_1A_2...A_n. We draw diagonals An2An\overline{A_{n-2}A_n}, A1An1\overline{A_1A_{n-1}} and we use the assumption on A1A2...An2A_1A_2...A_{n-2}, so M(n)M(n2)+2n4+2=n2M(n) \ge M(n-2) + 2 \ge n - 4 + 2 = n - 2.
We also prove by induction that M(n)n2M(n) \le n - 2 if nn is even and that M(n)n3M(n) \le n - 3 if nn is odd. Obviously, M(3)=0M(3) = 0 and M(4)=2M(4) = 2. Let us assume that the claim holds for all nn smaller than kk.
Let us consider a choice of diagonals of a convex kk-gon for which M(k)M(k) is achieved.
First case: if there are two good diagonals that intersect, they divide the kk-gon into 4 part, each having ai0a_i \ge 0 vertices, not counting the endpoints of these diagonals (for 1i41 \le i \le 4). Since there is no other segment that intersects these two diagonals, we have
M(k)=2+i=14M(ai+2)2+i=14(ai+22)=2+(k4)=k2. M(k) = 2 + \sum_{i=1}^{4} M(a_i + 2) \le 2 + \sum_{i=1}^{4} (a_i + 2 - 2) = 2 + (k - 4) = k - 2.
If kk is odd, then at least one of the numbers aia_i must also be odd, so we get the bound k3k - 3 in this case.
Second case: if there are no two good diagonals that intersect, then there is automatically at most k3k - 3 good diagonals as that is the maximal number of diagonals that we can draw from one vertex.

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.