In a convex $n$-gon, several diagonals are drawn. Among these diagonals, a diagonal is called good if it intersects exactly one other diagonal drawn (in the interior of the $n$-gon). Find the maximum number of good diagonals.
Problem
Source: All Russian-2014 Grade 9 Day 1 P3
Tags: induction, geometry, combinatorics proposed, combinatorics
21.05.2014 17:28
The answer is $n-2$ when $n$ is even, $n-3$ when $n$ is odd.
25.05.2014 14:17
It's quite easy to guess the correct answer. Here is my solution: We'll prove by induction that there are at most $n-2$ good diagonals when $n$ is even and $n-3$ when $n$ is odd. The initial steps ($n=3,4$) are trivial. For the induction step we distinguish two cases: $\bullet$ there are no good diagonals that intersect each other; Then if there are $m$ good diagonals, they will divide the polygon into $m+1$ zones, but the maximal number of zones is achieved by a triangulation, therefore $m\le n-3$. $\bullet$ there are 2 good diagonals $AC$ and $BD$ that intersect each other; Then (obviously) there are no drawn diagonals that cut one of $AC$ and $BD$ and this is the crucial fact. Denote by $x,y,z,t$ the number of points of the polygon that lie between $AB,BC,CD,DA,$ respectively. We have $x+y+z+t=n-4$. Now see that none of the chords $AB,BC,CD,DA$ can be a good diagonal. It follows that any other good diagonal must be a good diagonal in one of the polygons made by one of the sides of the quadrilateral $ABCD$ and some of the sides of the big polygon. Using the induction hypothesis we get that the number of good diagonals is at most $x+y+z+t+2$ when $n$ is even and $x+y+z+t+1$ when $n$ is odd beacause in this situation at least one of $x,y,z,t$ must be odd. Some models could be again easily found: $\bullet$ for a $2n+1$-gon with vertices labeled from $1$ to $2n+1$ draw the diagonals $[2,2n+1]$ and $[1,k]$ for all $k\in\{3,4,5,...,2n\}$; $\bullet$ for a $2n$-gon with vertices labeled from $1$ to $2n$ draw the diagonals $[i,2n+2-i]$ and $[j,2n-j]$ for all $i\in\{2,3,4,...,2n\}$ and $j\in\{1,2,3,...,2n-1\}$. Edit: I forgot to say that the case $n=2$ (which plays a vital role when one of $x,y,z,t$ is $0$) is done by a vacuum argument.
14.07.2014 19:13
There exists a more natural solution of this problem, which can be achieved without guessing. It is obvious that every good diagonal has its pair and that every good diagonal has exactly one pair.Now consider one pair of diagonals.Their end points form a quadriletal.So, every pair of good diagonals form a quadriletal.From the definition of good diagonal we easily obtain that none of those quadriletals has common area with any other quadriletal.So the problem is reduced in finding the maximum number of quadriletals that some n-tagon can be divided into,and that those quadriletals don't have common areas.By very trivial induction one is able to prove that for every n-tagon maximum number of such quadriletals is $ [\frac {n-2}{2}] $.As each quadriletal contains 2 diagonals the answer is: $ [\frac {n-2}{2}]*2 $ which is equivalent to your answer.
17.07.2014 03:43
@SmartClown It is not true that every good diagonal has its pair that forms a quadrilateral and that you can count them like that. Some good diagonals could intersect a non-good diagonal (for example, two good diagonals could intersect some other diagonal, making that diagonal not good) so your solution is not correct.
18.07.2014 18:00
But I am considering only quadriletals formed by pairs of good diagonals,so because they are all formed out of good diagonals they can't have any common area.Of course it is true that pair of good diagonals will surely intersect some other diagonal but that diagonal is not good so it can't make a quadriletal.It is of course true that i can count them like that.If what you are saying is truth i woud get result $ \frac{n(n-3)}{2} $ which is absurd.Also from the definition of good diagonal every diagonal must have exatcly one pair.
29.07.2014 23:19
The answer is n-2 for even n and n-3 for odd n.Now,we have 2 cases: 1)No 2 diagonals have a common point.It is easy to see that there are at most n-3 diagonals such that no 2 intersect each other. 2)If there exist two diagonals that intersect each other,they will divide the polygon into 4 parts and now just induct on these 4 polygons and we get the desired result(if a diagonal is not in any of these polygons,then it will intersect a good diagonal,so contradiction)
21.08.2020 12:01
The answer is $n-2$ for even $n$ and $n-3$ for odd $n$. Firstly, we provide a construction. For even $n$, we divide the convex $n$-gon into $\frac{n}{2}-1$ convex quadrilaterals, each of which generates $2$ good diagonals. For odd $n$, we take a random vertex $A$ from the convex $n$-gon and construct the $n-3$ diagonals with their endpoints being $A$. Afterwards, we construct the diagonal connecting the two neighboring vertices of $A$. [asy][asy] size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */pen dps = linewidth(0.7) + fontsize(0); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -25.760433772373936, xmax = 19.853864007011936, ymin = -27.005110383070985, ymax = 11.432112570887043; /* image dimensions */pen zzttqq = rgb(0.6,0.2,0); draw((-7.897491984642404,1.6234436428023074)--(-11.884755776546763,-0.2904429773117846)--(-12.874437274640187,-4.601100128282482)--(-10.121286125034878,-8.062515054047697)--(-5.698481297432332,-8.068171715509436)--(-2.9364850357941217,-4.61381053121214)--(-3.915136859589925,-0.3006359290583607)--cycle, linewidth(2) + zzttqq); draw((9.805959251412949,-8.504206388634762)--(14.191949422507744,-8.424461112796674)--(17.236924389393714,-5.266709295285295)--(17.157179113555628,-0.8807191241905006)--(13.999427296044248,2.1642558426954714)--(9.613437124949453,2.084510566857384)--(6.568462158063482,-1.0732412506539948)--(6.648207433901569,-5.45923142174879)--cycle, linewidth(2) + zzttqq); /* draw figures */draw((-7.897491984642404,1.6234436428023074)--(-11.884755776546763,-0.2904429773117846), linewidth(2) + zzttqq); draw((-11.884755776546763,-0.2904429773117846)--(-12.874437274640187,-4.601100128282482), linewidth(2) + zzttqq); draw((-12.874437274640187,-4.601100128282482)--(-10.121286125034878,-8.062515054047697), linewidth(2) + zzttqq); draw((-10.121286125034878,-8.062515054047697)--(-5.698481297432332,-8.068171715509436), linewidth(2) + zzttqq); draw((-5.698481297432332,-8.068171715509436)--(-2.9364850357941217,-4.61381053121214), linewidth(2) + zzttqq); draw((-2.9364850357941217,-4.61381053121214)--(-3.915136859589925,-0.3006359290583607), linewidth(2) + zzttqq); draw((-3.915136859589925,-0.3006359290583607)--(-7.897491984642404,1.6234436428023074), linewidth(2) + zzttqq); draw((-7.897491984642404,1.6234436428023074)--(-12.874437274640187,-4.601100128282482), linewidth(2)); draw((-7.897491984642404,1.6234436428023074)--(-10.121286125034878,-8.062515054047697), linewidth(2)); draw((-7.897491984642404,1.6234436428023074)--(-5.698481297432332,-8.068171715509436), linewidth(2)); draw((-7.897491984642404,1.6234436428023074)--(-2.9364850357941217,-4.61381053121214), linewidth(2)); draw((-3.915136859589925,-0.3006359290583607)--(-11.884755776546763,-0.2904429773117846), linewidth(2)); draw((9.805959251412949,-8.504206388634762)--(14.191949422507744,-8.424461112796674), linewidth(2) + zzttqq); draw((14.191949422507744,-8.424461112796674)--(17.236924389393714,-5.266709295285295), linewidth(2) + zzttqq); draw((17.236924389393714,-5.266709295285295)--(17.157179113555628,-0.8807191241905006), linewidth(2) + zzttqq); draw((17.157179113555628,-0.8807191241905006)--(13.999427296044248,2.1642558426954714), linewidth(2) + zzttqq); draw((13.999427296044248,2.1642558426954714)--(9.613437124949453,2.084510566857384), linewidth(2) + zzttqq); draw((9.613437124949453,2.084510566857384)--(6.568462158063482,-1.0732412506539948), linewidth(2) + zzttqq); draw((6.568462158063482,-1.0732412506539948)--(6.648207433901569,-5.45923142174879), linewidth(2) + zzttqq); draw((6.648207433901569,-5.45923142174879)--(9.805959251412949,-8.504206388634762), linewidth(2) + zzttqq); draw((6.568462158063482,-1.0732412506539948)--(17.157179113555628,-0.8807191241905006), linewidth(2) + dotted); draw((6.648207433901569,-5.45923142174879)--(17.236924389393714,-5.266709295285295), linewidth(2) + dotted); draw((9.613437124949453,2.084510566857384)--(17.157179113555628,-0.8807191241905006), linewidth(2)); draw((6.568462158063482,-1.0732412506539948)--(13.999427296044248,2.1642558426954714), linewidth(2)); draw((6.568462158063482,-1.0732412506539948)--(17.236924389393714,-5.266709295285295), linewidth(2)); draw((6.648207433901569,-5.45923142174879)--(17.157179113555628,-0.8807191241905006), linewidth(2)); draw((6.648207433901569,-5.45923142174879)--(14.191949422507744,-8.424461112796674), linewidth(2)); draw((9.805959251412949,-8.504206388634762)--(17.236924389393714,-5.266709295285295), linewidth(2)); /* dots and labels */dot((-7.897491984642404,1.6234436428023074),dotstyle); label("$A$", (-7.7380014329662306,2.022170021992753), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); [/asy][/asy] Now we prove the bound. Let the maximum number of good diagonal be $f(n)$, let $g(n)=n-f(n)$. We first show the following lemma Lemma. Suppose we chose $n-2$ diagoanls from a convex $n-$gon then at least two of them intersects in the interior of the polygon. Proof. It suffices to show that we can only choose $n-3$ diagonals which do not intersect in the interior of the polygon.We proceed by induction on $n$. The small cases are trivial. Suppose this holds for all smaller cases, we consider the case $n$. Consider any diagonal chosen, it will divide the convex $n-$gon into a convex $a$-gon and a convex $b$-gon, where $a+b=n+2$, notice that none of the other diagonals can pass through that diagonal. Therefore, any other diagonals are either a diagonal of the $a$-gon or the diagonal of the $b$-gon. From the inductive hypothesis there are at most $$a-3+b-3+1=n-3$$diagonals being chosen. $\blacksquare$ We now return to the original problem, again the small cases are obvious. We now consider the case $n$. By inductive hypothesis we have $g(a)=2$ for all even numbers smaller than $n$ and $g(b)=3$ for all odd numbers smaller than $n$. Suppose that there are at least $n-2$ good diagonals. From the lemma, two of them, which we denote by $l_1$ and $l_2$, intersect in the interior of the polygon. Now notice that $l_1$ and $l_2$ divide the convex $n-$gon into four polygons with $a,b,c,d$ sides respectively, where $a,b,c,d\geq 2$ and $a+b+c+d=n+4$. It is easy to see that the good diagonals of the $n-$ gon must be good diagonal a good diagonal of either one of the four small polygons. This implies $f(n)\leq n+4+2-(g(a)+g(b)+g(c)+g(d))$ If $n$ is odd then at least one of $a,b,c,d$ is odd hence $g(a)+g(b)+g(c)+g(d)\geq 9$, hence $f(n)\leq n-3$. If $n$ is even then $g(a)+g(b)+g(c)+g(d)\geq 8$ hence $f(n)\leq n-2$ as desired.
18.11.2021 01:00
I found a bit different solution
08.04.2023 11:04
kind of a same problem: given a convex n-gon, we can only have diagnols which intersect the other diagnols less than or equal to 1 time. find the maximum number of such diagnols
17.06.2023 01:55
11.02.2024 20:03
This problem is very similar to ARO 2011 9.3: the same approach works! The answer is $n-2$ when $n$ is even and $n-3$ when $n$ is odd. We strong induct on $n$; let $f(n)$ be the maximum number of good diagonals for an $n$-gon. Take some good diagonal $\ell$ in an $n$-gon; it intersects exactly one other diagonal $m$. The four distinct endpoints of $\ell$ and $m$ split the vertices $n$-gon into four continuous sections of $a, b, c, d$ vertices, respectively. Observe that there cannot exist another diagonal between two distinct sections, as it will intersect at least one of $m$ or $\ell$. As a result, any other good diagonals must be contained within one of the four sections of vertices. This is equivalent to the good diagonals being contained in one of the $a$-gon, $b$-gon, $c$-gon, or $d$-gon, as the only side of each of these polygons that was not a side in the original $n$-gon cannot be drawn anyways (as we cannot draw another diagonal that intersects it.) So we have the relation $$f(n) \leq f(a)+f(b)+f(c)+f(d) + 2 \leq (a-2)+(b-2)+(c-2)+(d-2) + 2 = n-2$$as $a+b+c+d = n+4$. When $n$ is odd, one of the $a, b, c, d$ must also be odd, so the similar inequality follows. The construction also follows inductively similarly.
30.08.2024 00:06
Seems sort of like a ISL 2016 C5 older brother, russian combi is interesting. We claim that the answer is $n-2$ for $n$ even and $n-3$ when $n$ is odd. We will prove this statement by induction the cases $n=3,4,5$ being trivial. Now suppose it's true for $n=k$, we will prove the statement for $n=k+1$. Case 1: No two good diagonals intersect In this case we will prove that maximun with this condition is $k-2$ achieved by a triangulation from one single vertex + closest diagonal to the vertex. Note that in fact there's at most $k-2$ diagonals that can be constructed without having two that intersect, and we will prove this by induction with cases $m=3,4$ being trivial, now if it was true for $m=\kappa$ then we prove it for $\kappa+1$. If for $\kappa+1$ we were able to get such $\kappa-1$ diagonals, consider one of them and divide the polygon in two $a,b$-gons where $a+b=\kappa+3$, now since no diagonal intersect we can apply inductive hypothesis on these two and see that we can have at most $\kappa-2=a+b-6+1$ which contradicts any construct with $\kappa-1$ diagonals, therefore the induction is complete and also this case. Case 2: At least one pair of good diagonals intersect. Notice that no diagonal can intersect them or else they stop being good so this pair divides the polygon in four regions with $a,b,c,d$ vertices respectively where $a+b+c+d=k+5$ and $a,b,c,d \ge 2$, now if $k+1$ is odd then at least one of $a,b,c,d$ is odd as well so WLOG it's $d$ then by inductive hypothesis on each region we have that we can have at most $k-2=a-2+b-2+c-2+d-3+2$ good diagonals, and if $k+1$ is even then we can have at most $k-1=a-2+b-2+c-2+d-2+2$ good diagonals which completes the induction. Therefore our claimed answer (construction for $n$ even is repeating construct for $n=4$ of the two diagonals intersecting) was correct thus we are done .