Let be a positive integer. Some diagonals are drawn in a convex -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 be the maximal possible number of good diagonals in a convex -gon.
We will show that if is even and if is odd. For any , we can draw all diagonals from one vertex and one more diagonal joining two vertices adjacent to if . We show by mathematical induction that if is even. For the claim is true as both diagonals in a convex quadrilateral are good. Let us assume that the claim is true for and consider a convex -gon . We draw diagonals , and we use the assumption on , so .
We also prove by induction that if is even and that if is odd. Obviously, and . Let us assume that the claim holds for all smaller than .
Let us consider a choice of diagonals of a convex -gon for which is achieved.
First case: if there are two good diagonals that intersect, they divide the -gon into 4 part, each having vertices, not counting the endpoints of these diagonals (for ). Since there is no other segment that intersects these two diagonals, we have
If is odd, then at least one of the numbers must also be odd, so we get the bound in this case.
Second case: if there are no two good diagonals that intersect, then there is automatically at most good diagonals as that is the maximal number of diagonals that we can draw from one vertex.