AoPS Academy
be real numbers less than 2.Then prove that 
be reals such that 
and 
Prove that
Where 
, let 
be the maximal number for an 
-gon, and for convenience set 
. Suppose the -gon has vertices 
, 
, ..., 
. Certainly, any optimal configuration contains at least one pair of crossing diagonals, say 
and 
. To any such configuration we can add the diagonals 
, 
, 
and 
if they do not already appear without creating any new crossings. Moreover, doing so makes clear that the problem decomposes into four smaller versions of the same problem, with 
, 
, 
and 
vertices. It follows immediately that![\[
f(n) = 6 + \max_{\substack{i, j, k \\ 1 < i < j < k \leq n}}( f(i) + f(j - i + 1) + f(k - j + 1) + f(n + 2 - k)).
\]](http://latex.artofproblemsolving.com/9/9/2/9928c1e79742876d8d65aff0734f2d5b88d50a56.png)
.
.
for example. If the pentagon is 
, we can draw 
in that order. This yields 
diagonals. In your formula, 
. 
is the last diagonal drawn, and 
is the only one crossing it, we can induct on the two polygons 
and 
, after which we are essentially done. 
. Base cases are obvious. Now, assume we have diagonals drawn on points 
. WLOG add point 
after and before . Then we can draw diagonals 
and then 
in that order. is the maximum, draw two n-gons side by side, each with diagonals that never cross. At best, we can get 
in each, super-imposing them gives is the best -- if any side has more, then we would have to draw a diagonal with two intersections.
. 
and 
cases are trivial.Now consider and 
.By considering the last drawn diagonal and by induction hypotesis(strong induction) applied on 
polygon the last diagonal divides the and of course adding for the last diagonal and the diagonal that is intersected by it we easily obtain: .
subsets such that no diagonals from the same subset intersect each other.It is done by greedy algorithm.Let the first diagonal drawn be colored blue.Now for every next diagonal drawn if it intersects a blue diagonal we color it red.Otherwise we color it blue.Now we easily see that no blue diagonals or red diagonals intersect each other so we proved that our subsets exist.Now number of diagonals in both subsets is 
so the maximum number is 
.Then we just give an example which is not hard.
. Let the polygon be 
. Now, go with 
and then 
for 
through 
. The only diagonals that can cross are 
and 
, the second of which comes after. On the other hand, the only diagonal that can ever cross is . Hence, this construction works. is the largest possible value. Let the answer for an -gon be , and observe that 
, 
. We use induction. Now look at the last drawn diagonal, and let it divide the polygon into an 
-gon and a 
-gon, where 
. Now see that there can be at most one diagonal that crosses the diagonal, and that the maximal number of diagonals completely within the -gon and the -gon sum to 
. Hence, it is clear that ![\[ f(n) \le f(a) + f(b) + 2 = 2(a+b-6) + 2 = 2(n-4) + 2 = 2(n-3) \]](http://latex.artofproblemsolving.com/8/9/7/897c7f127490a2070aa8c1ce47f4c2c1e46ecb7b.png)
, so our induction is complete and the answer is , as desired.
diagonals for general . Let the polygon be 
.
diagonals 
for 
, where indices are cyclic. Then, construct 
diagonals 
for 
, in that order.
be the last diagonal that was drawn. Then, intersects at most one other diagonal. All other diagonals must be contained in a 
-gon or 
-gon that partitions the -gon into, where 
. Thus, by the inductive hypothesis, the number of diagonals 
as needed.
.
-gon is . As a construction, in polygon 
, draw 
for 
and for 
, where indices are modulo .
. Let the final diagonal drawn in a 
-gon be . Note that intersects at most 
other diagonal by the problem condition. Furthermore, suppose that splits the -gon into an 
-gon and a 
-gon such that 
and 
. The total number of diagonals is hence![\[(2(a+1)-6)+(2(b+1)-6)+2=2a+2b-6=2k-6,\]](http://latex.artofproblemsolving.com/d/a/5/da5cbf33ba463e9cec4c4a5abcf94ce80e7a5e51.png)
into the general formula yields 
.
. The answer is diagonals. We proceed by using strong induction. The base cases and can be checked by hand.
be the diagonal that we draw last. There is at most one more diagonal that intersects . divides the points into 
and 
points (the two partitions are disjoint, except that they both share the common points of ), then we get that the maximum number of diagonals is,![\[ \le (2p-6) + (2q-6) + 2= 2p + 2q -10 = 2(p+q-2) -6. \]](http://latex.artofproblemsolving.com/a/0/7/a0702a76fa24ec52a65ba06a74bf00555353faa9.png)
in the first step are due to counting the two diagonals and 
.
-gon is 
. We will prove this using induction.
-side, this is obviously true.
sided polygon and a 
sided polygon. Note that 
.-sided polygon and the -sided polygon) is
.(we add two, because we count the last diagonal and the diagonal that intersects the last diagonal)
so we are done.
gon. Let 
denote the maximum number of diagonals Peter can draw for a gon. We proceed via induction.
since that is the maximum number of total diagonals we can draw in a quadrilateral (and you can draw both without any issue). Now, consider a gon for 
. Assume that for all 
we have that 
. Then, we simply consider the last diagonal drawn in the gon. This separates the gon into two polygons with 
and 
vertices each such that 
. Then,![\[d(n) = 2 + d(a+2)+d(b+2)= 2+ 2(a-1)+2(b-1)=2(a+b-1) = 2((a+b+2)-3)=2(n-3)\]](http://latex.artofproblemsolving.com/1/8/c/18c9ec46f708e456064e0313ca012066e8a9cb2e.png)
(Here the leading +2 is due to the last drawn diagonal and the one and only diagonal with intersects it (if there are two or more we are not able to draw the last diagonal)). Thus, the induction is complete.
gon is![\[d(2011)=2(2011-3)=2(2008)=4016\]](http://latex.artofproblemsolving.com/d/0/2/d029f5ac2b1f01dda1dd1b971502a5ca0088540f.png)
diagonals.
for any -gon. We can prove this bound and constructability through strong induction.-gon satisfies the inductive hypothesis given that 3-, 4-, 
, 
-gons all hold. Note that the last diagonal drawn divides the -gon into an 
-gon and a 
-gon. Also, this final diagonal must only intersect with at most one other diagonal, so our maximum bound is![\[(2m-6) + (2(k+2-m)-6) + 2 = 2k - 6,\]](http://latex.artofproblemsolving.com/8/0/2/8028640f8667299d53255d27735fbd2cda29ef2d.png)
(in order) and setting 
as the final diagonal and 
as the only diagonal crossing . We are left with a -gon that we can start constructing by drawing edges from 
, so we indeed have 
diagonals. 
-gon the greatest number of diagonals that can be drawn is . Base cases 
work.-gon into a 
-gon and a 
-gon where 
We also know that since most one diagonal intersects the last diagonal, at most one diagonal goes between the and gons. Thus, the maximal diagonals is 
diagonals is achievable for -gon. There exists a vertex, 
, on the -gon such that the number of diagonals going through it is at most (can be easily shown by contradiction). Let the neighbors of be 
Now to construct our -gon, insert a new vertex, 
beween and 
Finally draw the edges 
then 
This -gon will have 
edges, ad desired. \qed
but if you consider 
intersections, the answer appears to be 
...
. In a cylic fashion starting with , draw for 
in that order. Now from 
for 
in that order. This gives 
. gon into an gon and 
gon obviously. Then, we have a maximum of 
.
We proceed with induction on 
The base cases, are trivial. Now suppose that the proposition holds for all 
for some positive integer 
Then consider a 
-gon. Note that the last diagonal drawn intersects with at most one other diagonal. If this last diagonal separates the polygon into an -gon and a 
-gon, then by the inductive hypothesis we have at most 
Thus the bound is proven. For the construction, just consider construct diagonals of the form 
for 
and then diagonals of the form for 
Thus the induction is complete, so is indeed the answer.
.
Prove that
Let 
Prove that
yields 
yields 
work. Now, draw a diagonal through the 
gon and an 
gon. Then this gives us a new maximum of 
.
.
.
.