Maximize non-intersecting/perpendicular diagonals!

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

Maximize non-intersecting/perpendicular diagonals!

G H J

Reveal topic tags

combinatorics

IMO Shortlist

Extremal combinatorics

G H BBookmark kLocked kLocked NReply

Source: 2016 IMO Shortlist C5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cjquines0

510 posts

cjquines0

#1 h Jul 19, 2017, 4:32 PM • 6 Y

Y by anantmudgal09, Feddoceddo, megarnie, HWenslawski, Adventure10, Mango247

Let $n \geq 3$ be a positive integer. Find the maximum number of diagonals in a regular $n$ -gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#2 h Jul 19, 2017, 5:35 PM • 11 Y

Y by nguyenhaan2209, Imayormaynotknowcalculus, v4913, HamstPan38825, megarnie, HWenslawski, Iora, Adventure10, math_comb01, luti_nudli, bhan2025

The answer is $n-3$ when $n$ is odd, and $n-2$ when $n$ is even.

First, if $n$ is odd, then there are no perpendicular diagonals at all! (Look at the intercepted arcs.) Then, the maximum is just $n-3$ , achieved at any triangulation.

Now assume $n$ is even. We prove that $n-2$ is a maximum. Let $\mathcal P$ denote the polygon. Paint red any diagonal which intersects another diagonal inside $\mathcal P$ . If we consider two intersecting red diagonals $d_1$ and $d_2$ , we observe that they partition $\mathcal P$ into four regions, each of which does not contain a diameter of $\mathcal P$ . So any other diagonal intersecting $d_1$ or $d_2$ must be perpendicular to them. Consequently, all the red diagonals are parallel to either $d_1$ or $d_2$ , i.e.\ they all ``go in the same direction''.

$[asy] int N = 20; pair[] A = new pair[N]; size(7cm); for (int i=0; i<N; ++i) { A[i] = dir(360*i/N); } draw(unitcircle, lightblue); for (int i=0; i<N-1; ++i) { draw(A[i]--A[i+1], lightblue); } draw(A[N-1]--A[0], lightblue); draw(A[6]--A[14], red); draw(A[10]--A[0], red); draw(A[7]--A[13]--A[17]--A[3]--cycle, red); draw(A[8]--A[12]--A[18]--A[2]--cycle, red); draw(A[8]--A[10], grey); draw(A[12]--A[10], grey); draw(A[4]--A[6]--A[3], grey); draw(A[0]--A[2], grey); draw(A[0]--A[18], grey); draw(A[15]--A[17]--A[14], grey); for (int i=0; i<N; ++i) { dot((string) i, A[i], A[i], blue); } [/asy]$

Now a double-count will finish from here. Suppose that there are $k$ red diagonals. Note that the longest red diagonals in each direction are not the vertices of a red rectangle. So at most $n-(k+2)$ vertices touch no red diagonal. Each such vertex can contribute an additional diagonal in the region of the mesh. So the total number is at most $k + \left( n-(k+2) \right) = n-2$ .

In particular, equality is sharp as long as only two red diagonals are not part of a red rectangle, and each of the remaining regions is triangulated as much as possible. Some particular examples:

For even $n$ , one may take just two red diagonals.
When $4 \mid n$ , one may take all diagonals parallel to two perpendicular major diagonals.
\dots

Remark: This is a very global problem, with multiple equality cases motivating the double-counting. (Thus it is pretty rigid.)

Remark: There is not much special about a regular $n$ -gon in this solution. In fact, any cyclic polygon has at most $n-2$ diagonals as described.

This post has been edited 1 time. Last edited by v_Enhance, Aug 9, 2018, 8:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

anantmudgal09

1979 posts

anantmudgal09

#3 h Sep 25, 2017, 6:54 PM • 3 Y

Y by Generic_Username, rashah76, Adventure10

cjquines0 wrote:

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kayak

1298 posts

Kayak

#4 h Jul 29, 2018, 6:33 PM • 2 Y

Y by Adventure10, Mango247

Long and possibly wrong solution

@v_enhance

This post has been edited 5 times. Last edited by Kayak, Jul 29, 2018, 8:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#5 h Aug 9, 2018, 8:33 PM • 8 Y

Y by enhanced, Kayak, dchenmathcounts, v4913, HamstPan38825, Adventure10, Mango247, MS_asdfgzxcvb

@Kayak: by "points" I mean vertices of the $n$ -gon. The claim is at most $n-(k+2)$ vertices are not the endpoint of any red diagonal.

The "global"/"rigid" is, err, a bit hard to describe. Sorry, I copy-pasted that from my internal notes... hadn't meant to post that. (I'll try to explain but it may not make sense: roughly "global" means that you 're taking a big sum over an entire space, and the "rigid" means there's not much freedom and that all the constructions achieving equality are of a certain shape, and you want to understand that shape pretty well.)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kayak

1298 posts

Kayak

#6 h Aug 9, 2018, 8:56 PM • 4 Y

Y by dchenmathcounts, v_Enhance, Adventure10, Mango247

Thanks for replying

!

Some days after I posted the above post I came across one of your blog posts which clarifies what global means to some extend .

v_enhance wrote:

For example, one of the unusual themes I teach is called Global. It’s about the idea that to solve a problem, you can just kind of “add up everything at once”, for example using linearity of expectation, or by double-counting, or whatever. In particular these kinds of approach ignore the “local” details of the problem. It’s hard to make this precise, so I’ll just give two recent examples.

You also wrote about "rigid" there, I'm putting this up so people don't have to go through the link

v_enhance wrote:

These thoughts led to the recent development of a class which I named Rigid, which is all about problems where the point is not to immediately try to prove what the question asks for, but to first step back and understand completely how a particular rigid structure (like the {\varphi} in this problem) behaves, and to then solve the problem using this understanding.

And since this is an extremal combinatorics and also a problem with a "random condition", I think you mean by rigid is what David Yang meant by

pythag011,http://artofproblemsolving.com/community/c5h420845p2384302 wrote:

Exceedingly Random Condition => Don't try to use that condition at the start
Extremely Unflexible Structure => Extremal principle

(BTW, Also please post such remarks on AoPS too (instead of confining them to your notes) so that after someone searches your posts using the keywords "global" or "rigid" one can find such problems and see the connection between them

)

This post has been edited 2 times. Last edited by Kayak, Aug 10, 2018, 6:44 AM
Reason: efg

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shankarmath

544 posts

shankarmath

#7 h Feb 22, 2019, 10:56 PM • 1 Y

Y by Adventure10

Cool

This post has been edited 2 times. Last edited by shankarmath, Feb 27, 2019, 2:15 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mastermind.hk16

143 posts

mastermind.hk16

#8 h Feb 23, 2019, 3:21 AM • 4 Y

Y by shankarmath, HolyMath, Adventure10, Mango247

I claim that the answer is $n-3$ when $n$ is odd and $n-2$ when $n$ is even.
For that the following constructions work,

$[asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -7.14, xmax = 12.58, ymin = 1.91, ymax = 13.77; /* image dimensions */ pen rvwvcq = rgb(0.08235294117647059,0.396078431372549,0.7529411764705882); pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); draw((-5.08,7.41)--(-3.62,7.37)--(-2.678431629987527,8.486534372328975)--(-2.9643150770764732,9.91882996147269)--(-4.262374274649304,10.588338975300422)--(-5.595144171351539,9.990907470904885)--(-5.959021851415031,8.576413556477673)--cycle, linewidth(2) + rvwvcq); draw((-0.06,7.43)--(1.38,7.45)--(2.3840916292848964,8.48237590053236)--(2.3640916292848964,9.922375900532359)--(1.3317157287525372,10.926467529817256)--(-0.10828427124746232,10.906467529817256)--(-1.1123759005323592,9.874091629284896)--(-1.0923759005323594,8.434091629284897)--cycle, linewidth(2) + rvwvcq); /* draw figures */ draw((-5.08,7.41)--(-3.62,7.37), linewidth(2) + rvwvcq); draw((-3.62,7.37)--(-2.678431629987527,8.486534372328975), linewidth(2) + rvwvcq); draw((-2.678431629987527,8.486534372328975)--(-2.9643150770764732,9.91882996147269), linewidth(2) + rvwvcq); draw((-2.9643150770764732,9.91882996147269)--(-4.262374274649304,10.588338975300422), linewidth(2) + rvwvcq); draw((-4.262374274649304,10.588338975300422)--(-5.595144171351539,9.990907470904885), linewidth(2) + rvwvcq); draw((-5.595144171351539,9.990907470904885)--(-5.959021851415031,8.576413556477673), linewidth(2) + rvwvcq); draw((-5.959021851415031,8.576413556477673)--(-5.08,7.41), linewidth(2) + rvwvcq); draw((-4.262374274649304,10.588338975300422)--(-5.08,7.41), linewidth(2) + wrwrwr); draw((-4.262374274649304,10.588338975300422)--(-3.62,7.37), linewidth(2) + wrwrwr); draw((-4.262374274649304,10.588338975300422)--(-2.678431629987527,8.486534372328975), linewidth(2) + wrwrwr); draw((-4.262374274649304,10.588338975300422)--(-5.959021851415031,8.576413556477673), linewidth(2) + wrwrwr); draw((-0.06,7.43)--(1.38,7.45), linewidth(2) + rvwvcq); draw((1.38,7.45)--(2.3840916292848964,8.48237590053236), linewidth(2) + rvwvcq); draw((2.3840916292848964,8.48237590053236)--(2.3640916292848964,9.922375900532359), linewidth(2) + rvwvcq); draw((2.3640916292848964,9.922375900532359)--(1.3317157287525372,10.926467529817256), linewidth(2) + rvwvcq); draw((1.3317157287525372,10.926467529817256)--(-0.10828427124746232,10.906467529817256), linewidth(2) + rvwvcq); draw((-0.10828427124746232,10.906467529817256)--(-1.1123759005323592,9.874091629284896), linewidth(2) + rvwvcq); draw((-1.1123759005323592,9.874091629284896)--(-1.0923759005323594,8.434091629284897), linewidth(2) + rvwvcq); draw((-1.0923759005323594,8.434091629284897)--(-0.06,7.43), linewidth(2) + rvwvcq); draw((-0.06,7.43)--(2.3840916292848964,8.48237590053236), linewidth(2) + wrwrwr); draw((-0.10828427124746232,10.906467529817256)--(-1.0923759005323594,8.434091629284897), linewidth(2) + wrwrwr); draw((-0.10828427124746232,10.906467529817256)--(-0.06,7.43), linewidth(2) + wrwrwr); draw((-0.10828427124746232,10.906467529817256)--(1.38,7.45), linewidth(2) + wrwrwr); draw((-0.10828427124746232,10.906467529817256)--(2.3840916292848964,8.48237590053236), linewidth(2) + wrwrwr); draw((-0.10828427124746232,10.906467529817256)--(2.3640916292848964,9.922375900532359), linewidth(2) + wrwrwr); /* dots and labels */ dot((-5.08,7.41),dotstyle); dot((-3.62,7.37),dotstyle); dot((-2.678431629987527,8.486534372328975),dotstyle); dot((-2.9643150770764732,9.91882996147269),dotstyle); dot((-4.262374274649304,10.588338975300422),dotstyle); dot((-5.595144171351539,9.990907470904885),dotstyle); dot((-5.959021851415031,8.576413556477673),dotstyle); dot((-0.06,7.43),dotstyle); dot((1.38,7.45),dotstyle); dot((2.3840916292848964,8.48237590053236),dotstyle); dot((2.3640916292848964,9.922375900532359),dotstyle); dot((1.3317157287525372,10.926467529817256),dotstyle); dot((-0.10828427124746232,10.906467529817256),dotstyle); dot((-1.1123759005323592,9.874091629284896),dotstyle); dot((-1.0923759005323594,8.434091629284897),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy]$

Now we will prove these bounds are maximal.

Case 1: $n$ is odd

Claim 1: In any regular odd polygon, no two diagonals are perpendicular.
Proof: AFSOC, two diagonals are perpendicular. Reflect the diagonals across two lines of symmetry to form a rectangle. Then the number of vertices are even. Contradiction.

Claim 2: The maximum number of diagonals in any cyclic polygon such that no two intersect in its interior is $n-3$ .

Proof: We will prove this by strong induction. The base case is trivial. Assume Claim 2 holds for all cyclic polygons with less than $g$ sides. Now draw a diagonal in a cyclic $g$ -gon. It divides it into an $l$ -gon and an $m$ -gon such that $m+l=g+2$ . Apply the Induction hypothesis on these smaller polygons. We have at maximum $m-3 + l-3 +1 = g-3$ diagonals. So our claim is proved.

By Claim 1, no two diagonals can intersect in the interior of the polygon. We are done by Claim 2.

Case 2: $n$ is even
Consider the following set of diagonals $\mathcal{S}$ , such that if $\ell_1 \in \mathcal{S}$ , then $\exists \ \ell_2 \in \mathcal{S}$ such that $\ell_1 \perp \ell_2$ and $\ell_1, \ell_2$ intersect in the interior of the polygon.
Define a \textit{region} to be a set of consecutive vertices such that the first and last vertices are endpoints of some diagonals and all other vertices have no diagonals emanating from them.
For a fixed $|\mathcal{S}|=k$ we want to find the minimal number of regions, say $r_k$ .

Note the following observations:
1. Diagonals of $\mathcal{S}$ can only have one of two directions; N-S or E-W
2. Call a vertex \textit{occupied} if it is one of the endpoints of any diagonal in $S$ and \textit{unoccupied} otherwise. Suppose we have a set $\mathcal{S}$ of diagonals with $|\mathcal{S}|=k$ and we want to draw a new diagonal so that $|\mathcal{S}|=k+1$ . Then, if the new diagonal has $\epsilon$ unoccupied endpoints, then $r_{k+1}= r_k + \epsilon$ where $\epsilon \in \{ 0,1,2 \}$ .

Suppose we are constructing $\mathcal{S}$ with $|\mathcal{S}|=i$ . To minimize $r_i$ we need to minimize the number of vertices that act as endpoints of the diagonals in $\mathcal{S}$ . To do this, classify three types of rectangles (shown in solid line);

$[asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(15cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -9.31, xmax = 20.27, ymin = -4.71, ymax = 13.08; /* image dimensions */ pen rvwvcq = rgb(0.08235294117647059,0.396078431372549,0.7529411764705882); pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); draw((-4.68,0.17)--(-2.92,0.21)--(-1.4157952893393881,1.1246410161513771)--(-0.5704363054907651,2.6688457268119894)--(-0.6104363054907651,4.428845726811989)--(-1.5250773216421414,5.933050437472601)--(-3.069282032302754,6.778409421321224)--(-4.829282032302753,6.738409421321224)--(-6.333486742963366,5.823768405169848)--(-7.178845726811989,4.2795636945092355)--(-7.13884572681199,2.519563694509237)--(-6.224204710660613,1.0153589838486234)--cycle, linewidth(2) + rvwvcq); draw((4.48,0.335)--(6.24,0.375)--(7.744204710660612,1.2896410161513772)--(8.589563694509234,2.83384572681199)--(8.549563694509235,4.593845726811989)--(7.634922678357858,6.098050437472601)--(6.090717967697245,6.943409421321224)--(4.330717967697246,6.903409421321225)--(2.8265132570366336,5.988768405169848)--(1.9811542731880105,4.444563694509235)--(2.0211542731880097,2.6845636945092366)--(2.935795289339387,1.1803589838486235)--cycle, linewidth(2) + rvwvcq); draw((13.48,0.335)--(15.24,0.375)--(16.74420471066061,1.2896410161513772)--(17.589563694509234,2.83384572681199)--(17.549563694509235,4.593845726811989)--(16.634922678357857,6.098050437472601)--(15.090717967697245,6.943409421321224)--(13.330717967697247,6.903409421321225)--(11.826513257036634,5.988768405169848)--(10.981154273188011,4.444563694509235)--(11.02115427318801,2.6845636945092366)--(11.935795289339387,1.1803589838486235)--cycle, linewidth(2) + rvwvcq); /* draw figures */ draw((-4.68,0.17)--(-2.92,0.21), linewidth(2) + rvwvcq); draw((-2.92,0.21)--(-1.4157952893393881,1.1246410161513771), linewidth(2) + rvwvcq); draw((-1.4157952893393881,1.1246410161513771)--(-0.5704363054907651,2.6688457268119894), linewidth(2) + rvwvcq); draw((-0.5704363054907651,2.6688457268119894)--(-0.6104363054907651,4.428845726811989), linewidth(2) + rvwvcq); draw((-0.6104363054907651,4.428845726811989)--(-1.5250773216421414,5.933050437472601), linewidth(2) + rvwvcq); draw((-1.5250773216421414,5.933050437472601)--(-3.069282032302754,6.778409421321224), linewidth(2) + rvwvcq); draw((-3.069282032302754,6.778409421321224)--(-4.829282032302753,6.738409421321224), linewidth(2) + rvwvcq); draw((-4.829282032302753,6.738409421321224)--(-6.333486742963366,5.823768405169848), linewidth(2) + rvwvcq); draw((-6.333486742963366,5.823768405169848)--(-7.178845726811989,4.2795636945092355), linewidth(2) + rvwvcq); draw((-7.178845726811989,4.2795636945092355)--(-7.13884572681199,2.519563694509237), linewidth(2) + rvwvcq); draw((-7.13884572681199,2.519563694509237)--(-6.224204710660613,1.0153589838486234), linewidth(2) + rvwvcq); draw((-6.224204710660613,1.0153589838486234)--(-4.68,0.17), linewidth(2) + rvwvcq); draw((-6.333486742963366,5.823768405169848)--(-1.5250773216421414,5.933050437472601), linewidth(2) + wrwrwr); draw((-1.5250773216421414,5.933050437472601)--(-1.4157952893393881,1.1246410161513771), linewidth(2) + wrwrwr); draw((-1.4157952893393881,1.1246410161513771)--(-6.224204710660613,1.0153589838486234), linewidth(2) + wrwrwr); draw((-6.224204710660613,1.0153589838486234)--(-6.333486742963366,5.823768405169848), linewidth(2) + wrwrwr); draw((-7.178845726811989,4.2795636945092355)--(-0.6104363054907651,4.428845726811989), linewidth(2) + linetype("2 2") + wrwrwr); draw((-4.829282032302753,6.738409421321224)--(-4.68,0.17), linewidth(2) + linetype("2 2") + wrwrwr); draw((4.48,0.335)--(6.24,0.375), linewidth(2) + rvwvcq); draw((6.24,0.375)--(7.744204710660612,1.2896410161513772), linewidth(2) + rvwvcq); draw((7.744204710660612,1.2896410161513772)--(8.589563694509234,2.83384572681199), linewidth(2) + rvwvcq); draw((8.589563694509234,2.83384572681199)--(8.549563694509235,4.593845726811989), linewidth(2) + rvwvcq); draw((8.549563694509235,4.593845726811989)--(7.634922678357858,6.098050437472601), linewidth(2) + rvwvcq); draw((7.634922678357858,6.098050437472601)--(6.090717967697245,6.943409421321224), linewidth(2) + rvwvcq); draw((6.090717967697245,6.943409421321224)--(4.330717967697246,6.903409421321225), linewidth(2) + rvwvcq); draw((4.330717967697246,6.903409421321225)--(2.8265132570366336,5.988768405169848), linewidth(2) + rvwvcq); draw((2.8265132570366336,5.988768405169848)--(1.9811542731880105,4.444563694509235), linewidth(2) + rvwvcq); draw((1.9811542731880105,4.444563694509235)--(2.0211542731880097,2.6845636945092366), linewidth(2) + rvwvcq); draw((2.0211542731880097,2.6845636945092366)--(2.935795289339387,1.1803589838486235), linewidth(2) + rvwvcq); draw((2.935795289339387,1.1803589838486235)--(4.48,0.335), linewidth(2) + rvwvcq); draw((2.8265132570366336,5.988768405169848)--(7.634922678357858,6.098050437472601), linewidth(2) + wrwrwr); draw((7.634922678357858,6.098050437472601)--(7.744204710660612,1.2896410161513772), linewidth(2) + wrwrwr); draw((2.935795289339387,1.1803589838486235)--(2.8265132570366336,5.988768405169848), linewidth(2) + wrwrwr); draw((1.9811542731880105,4.444563694509235)--(8.549563694509235,4.593845726811989), linewidth(2) + linetype("2 2") + wrwrwr); draw((4.330717967697246,6.903409421321225)--(4.48,0.335), linewidth(2) + linetype("2 2") + wrwrwr); draw((2.0211542731880097,2.6845636945092366)--(8.589563694509234,2.83384572681199), linewidth(2) + wrwrwr); draw((13.48,0.335)--(15.24,0.375), linewidth(2) + rvwvcq); draw((15.24,0.375)--(16.74420471066061,1.2896410161513772), linewidth(2) + rvwvcq); draw((16.74420471066061,1.2896410161513772)--(17.589563694509234,2.83384572681199), linewidth(2) + rvwvcq); draw((17.589563694509234,2.83384572681199)--(17.549563694509235,4.593845726811989), linewidth(2) + rvwvcq); draw((17.549563694509235,4.593845726811989)--(16.634922678357857,6.098050437472601), linewidth(2) + rvwvcq); draw((16.634922678357857,6.098050437472601)--(15.090717967697245,6.943409421321224), linewidth(2) + rvwvcq); draw((15.090717967697245,6.943409421321224)--(13.330717967697247,6.903409421321225), linewidth(2) + rvwvcq); draw((13.330717967697247,6.903409421321225)--(11.826513257036634,5.988768405169848), linewidth(2) + rvwvcq); draw((11.826513257036634,5.988768405169848)--(10.981154273188011,4.444563694509235), linewidth(2) + rvwvcq); draw((10.981154273188011,4.444563694509235)--(11.02115427318801,2.6845636945092366), linewidth(2) + rvwvcq); draw((11.02115427318801,2.6845636945092366)--(11.935795289339387,1.1803589838486235), linewidth(2) + rvwvcq); draw((11.935795289339387,1.1803589838486235)--(13.48,0.335), linewidth(2) + rvwvcq); draw((10.981154273188011,4.444563694509235)--(17.549563694509235,4.593845726811989), linewidth(2) + wrwrwr); draw((11.02115427318801,2.6845636945092366)--(17.589563694509234,2.83384572681199), linewidth(2) + wrwrwr); draw((13.330717967697247,6.903409421321225)--(13.48,0.335), linewidth(2) + wrwrwr); draw((15.090717967697245,6.943409421321224)--(15.24,0.375), linewidth(2) + wrwrwr); draw((11.935795289339387,1.1803589838486235)--(11.826513257036634,5.988768405169848), linewidth(2) + linetype("2 2") + wrwrwr); draw((11.826513257036634,5.988768405169848)--(16.634922678357857,6.098050437472601), linewidth(2) + linetype("2 2") + wrwrwr); label("Awesome rectangle",(-5.98,-0.24),SE*labelscalefactor); label("Good rectangle",(3.65,-0.06),SE*labelscalefactor); label("Bad rectangle",(13.01,0.12),SE*labelscalefactor); /* dots and labels */ dot((-4.68,0.17),dotstyle); dot((-2.92,0.21),dotstyle); dot((-1.4157952893393881,1.1246410161513771),dotstyle); dot((-0.5704363054907651,2.6688457268119894),dotstyle); dot((-0.6104363054907651,4.428845726811989),dotstyle); dot((-1.5250773216421414,5.933050437472601),dotstyle); dot((-3.069282032302754,6.778409421321224),dotstyle); dot((-4.829282032302753,6.738409421321224),dotstyle); dot((-6.333486742963366,5.823768405169848),dotstyle); dot((-7.178845726811989,4.2795636945092355),dotstyle); dot((-7.13884572681199,2.519563694509237),dotstyle); dot((-6.224204710660613,1.0153589838486234),dotstyle); dot((4.48,0.335),dotstyle); dot((6.24,0.375),dotstyle); dot((7.744204710660612,1.2896410161513772),dotstyle); dot((8.589563694509234,2.83384572681199),dotstyle); dot((8.549563694509235,4.593845726811989),dotstyle); dot((7.634922678357858,6.098050437472601),dotstyle); dot((6.090717967697245,6.943409421321224),dotstyle); dot((4.330717967697246,6.903409421321225),dotstyle); dot((2.8265132570366336,5.988768405169848),dotstyle); dot((1.9811542731880105,4.444563694509235),dotstyle); dot((2.0211542731880097,2.6845636945092366),dotstyle); dot((2.935795289339387,1.1803589838486235),dotstyle); dot((13.48,0.335),dotstyle); dot((15.24,0.375),dotstyle); dot((16.74420471066061,1.2896410161513772),dotstyle); dot((17.589563694509234,2.83384572681199),dotstyle); dot((17.549563694509235,4.593845726811989),dotstyle); dot((16.634922678357857,6.098050437472601),dotstyle); dot((15.090717967697245,6.943409421321224),dotstyle); dot((13.330717967697247,6.903409421321225),dotstyle); dot((11.826513257036634,5.988768405169848),dotstyle); dot((10.981154273188011,4.444563694509235),dotstyle); dot((11.02115427318801,2.6845636945092366),dotstyle); dot((11.935795289339387,1.1803589838486235),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy]$
It is clear that, we need to maximize the number of awesome rectangles. Good rectangles and bad rectangles unnecessarily add vertices to $\mathcal{S}$ . Furthermore, no rectangles are just as bad as bad rectangles since all endpoints of all diagonals are unoccupied.
Note that the dotted diagonals are prerequisites by the definition of $\mathcal{S}$ for having any rectangle. So, by default, we always have $4$ regions made by the two dotted lines. Then we start constructing as many awesome rectangles as possible, $\lfloor \frac{i-2}{4} \rfloor$ . Each rectangle adds 4 additional regions. With the remaining diagonals, start forming a new awesome rectangle. We are ready to compute $r_i$ .
If $i \not \equiv 2 \mod 4$
$r_i = 4+4 \lfloor \frac{i-2}{4} \rfloor +4 \{\frac{i-2}{4} \}+1 = i+3$ If $i \equiv 2 \mod 4$
$r_i = i+2$ Now, for each region, we will draw diagonals $\not \in \mathcal{S}$ . Hence, all diagonals must be contained within the region. Apply Claim 1. If a region has $u$ vertices than, the number of diagonals $\not \in \mathcal{S}$ that can be drawn is $u-3+1 =u-2$ , since one side of the $u$ -gon is not drawn. Let $u_j$ denote the number of vertices in each region. Since endpoints are counted twice,
$\sum_{j=1} ^{r_i} u_j = n+r_i$ . So the the maximal number of diagonals is $\sum_{j=1} ^{r_i} (u_j-2) + i = n - r_i +i \leq n- (i+2)+i = n-2$ Of course we cannot have $n< r_i$ . When $i$ is large enough, $r_i =n$ , then $n-r_i + i = i \leq r_i-2 = n-2$ And so we are done.

This post has been edited 2 times. Last edited by mastermind.hk16, Feb 23, 2019, 3:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yayups

1614 posts

yayups

#9 h Aug 31, 2019, 8:40 AM • 1 Y

Y by Adventure10

We claim that the answer for $n$ odd is $n-3$ and for $n$ even is $n-2$ . The equality case for $n$ odd is any triangulation, and for $n$ even is connecting $P_0$ to $P_2,\ldots,P_{n-2}$ and also connecting $P_{n/2-1}$ to $P_{n/2+1}$ where we label the vertices $P_0,\ldots,P_{n-1}$ in order.

We claim that no two chords can be perpendicular if $n$ is odd. Indeed, each chord has an angle a multiple of $\pi/n$ to some given reference chord, which can never be $\pi/2$ . Thus, we can only add diagonals that never intersect each other, which means that we have at most $n-3$ diagonals (this can easily be proven by induction, and it's quite standard, so we leave the proof out here).

The interesting case is when $n$ is even. Firstly, suppose that we have at least one interior intersection point, since otherwise we have the trivial triangulation bound of $n-3$ , which is obviously at most $n-2$ . Note that each of the four split regions we get on the circle due to the chords in this intersection are strictly smaller than a half circle, so any other intersection of perpendicular chords would have to intersect this fundamental pair. Thus, all intersecting chords are in one of two perpendicular directions, call them horizontal and vertical. Call the intersecting chords the prominent chords, so we have horizontal and vertical prominent chords.

Let there be $x$ vertical prominent chords and $y$ horizontal prominent chords. Furthermore, let the number of vertices where a horizontal prominent chord and a vertical prominent chord meet is $p$ . Note that there $2x+2y-p$ regions along the circumference of the circle. In any region with $r$ points, we see that there are at most $r$ diagonals that we can add that don't intersect any other diagonals. However, if this region is bounded by a single prominent chord, then there are at most $r-1$ diagonals that can be formed.

Naively, we see that the number of total diagonals is at most $(x+y)+[n-(2x+2y-p)]=n-(x+y-p)$ . Suppose there are at least $n-1$ diagonals. If $x+y-p\ge 2$ , then we have $\le n-2$ diagonals, so $x+y-p\le 1$ . Similarly, if there are two regions bounded by single prominent chords, then the total number of diagonals is at most
$(x+y)+[n-(2x+2y-p)-2]\le n-(x+y-p)-2,$ so we have $\le n-2$ diagonals (we'll show that $x+y-p\ge 0$ in a moment). So we have further that there is at most one region bounded by a single prominent chord.

Consider the set of rectangles formed by prominent chords. Note that deleting them doesn't change the value of $x+y-p$ , so eventually we have no rectangles. Now, removing a diagonal at a point where two prominent chords meet on the circle makes $x+y-p$ not change, so we may assume now that $p=0$ . At this point, $x,y\ge 0$ , so $x+y-p\ge 0$ .

Again, consider the set of rectangles formed by prominent chords, and suppose $R_1$ is the narrowest one, so the one with smallest horizontal length. If there is no vertical chord cutting its horizontal edges, then we have two regions bounded only by a single prominent chord, which is a contradiction. Thus, there is a vertical chord cutting through its horizontal edges. Similarly, there is a horizontal chord cutting through the vertical edges of the widest rectangle. Repeating the rectangle deleting argument, we may assume for the purposes of computing $x+y-p$ that we have removed all the rectangles. Now, remove chords touching at one of the remaining $p$ points, but never deleting the two special horizontal and vertical chords we got just now. Thus, at the end, we have $p=0$ , and $x,y\ge 1$ , so $x+y-p\ge 2$ , which is a contradiction.

Thus, we always get a contradiction, so there are at most $n-2$ diagonals in the $n$ even case, as desired.

This post has been edited 1 time. Last edited by yayups, Aug 31, 2019, 8:41 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Wizard_32

1566 posts

Wizard_32

#10 h Sep 13, 2019, 3:02 AM • 1 Y

Y by Adventure10

I am posting my solution since it uses a different algebra-based approach (though similar in spirit).

cjquines0 wrote:

Hidden due to length

This post has been edited 6 times. Last edited by Wizard_32, Sep 13, 2019, 3:38 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pad

1671 posts

pad

#11 h Oct 17, 2019, 7:25 AM • 2 Y

Y by Adventure10, Mango247

We claim that the maximum number of diagonals is $n-2$ if $n$ is even and $n-3$ if $n$ is odd.

If $n$ is odd, we cannot have any perpendicular diagonals in the interior, so we simply triangulate the $n$ -gon. There are $n-3$ diagonals.

Assume $n$ is even. There will be a central axis to the diagram. Call the direction parallel to the central axis vertical and the direction perpendicular to the central axis horizontal. Call a diagonal criss-crossed if it intersects with another diagonal in the interior (perpendicularly), and up-and-down otherwise. If there are no criss-crossed diagonals, we connect vertices which are symmetric about the central axis and connect these lines with one of the adjacent lines. There are $n-2$ diagonals in this configuration. Otherwise, there exists a criss-crossed diagonal. (Assume WLOG that it is horizontal). Now, note that every other criss-crossed diagonal is either parallel or perpendicular to the original criss-crossed diagonal.

Notice that for any any configuration, we can decompose it into sets of (1) up-and-down diagonals, and (2) a set of criss-crossed diagonals. In other to maximize the number of diagonals in (2), we create a mesh, which is basically where we make rectangles symmetric about the central axis, starting at the top and making them succesively wider, till we stop at a certain point. Note that the central axis is included in the mesh. In order to maximize the number of diagonals in (1), we triangulate these ``outer'' regions.

Now comes the key part of the argument. We claim that we can have no more than $n-2$ diagonals total in the above description. Suppose the mesh contains $m$ vertices. Then, since each of the vertices in the mesh is part of one horizontal and one vertical criss-cross diagonal, excpet for the diagonal on the central axis, there are $m-2$ criss-cross diagonals in the mesh. There are $n-m$ vertices not connetced to a criss-cross diagonal. Say some outer region has $x$ vertices, which are not part of the mesh. Then we can triangulate this outer region with these $x$ vertices, and we can take one more vertex from an adjacent criss-crossed diagonal. (This would be clearer with a diagram, but oh well). We can triangulate this with $x$ diagonals, since we have $x$ vertices and one vertex adjacent to it from the mesh. So the total number of diagonals in the outer regions is $\sum_{\text{outer regions}} x = n-m$ . Therefore, the total number of diagonals is at most $(n-m)+(m-2) = n-2$ .

Note that we achieve equality for $n$ even when there are no outer regions, just the full mesh.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

william122

1576 posts

william122

#12 h Apr 28, 2020, 6:46 PM

Y by

If $n$ is odd, there are no perpendicular diagonals, so the best we can do is a triangulation, which gives $n-3$ edges.

If $n$ is even, note that all intersecting diagonals must be perpendicular with each other since a pair of intersecting diagonals takes up more than half of the perimeter of the $n$ -gon. So, if we consider only the diagonals which intersect with others, they form a perpendicular mesh. Clearly, once this mesh has been determined, the number of diagonals is maximized by triangulating the portions of the perimeter the mesh splits the n-gon into. For a region of size $k$ , this takes $k-2$ edges. Suppose there are $x$ vertices which are endpoints of exactly 1 mesh diagonal, and $y$ which are part of 2. Then, we have $\frac{x+2y}{2}$ mesh diagonals, which split the figure into $x+y$ parts. Thus, we need $\frac{x+2y}{2}+n+x+y-2(x+y)=n-\frac{x}{2}$ diagonals. Of course, $x\ge 4$ , since we need a lone vertical and lone horizontal diagonal in order to ensure that all diagonals in the mesh indeed intersect another diagonal. Thus, the maximum is $n-2$ diagonals, which is easily constructible.

This post has been edited 1 time. Last edited by william122, Apr 28, 2020, 6:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sriraamster

1492 posts

sriraamster

#13 h May 13, 2020, 3:56 AM • 2 Y

Y by Kagebaka, smartninja2000

Finally I make diagrams.

The answer is $n - 3$ if $n$ is odd and $n - 2$ if $n$ is even.

Think instead of the $n$ points as $n$ equally spaced points along a circle. Label these points $1, \dots n,$ and let the diagonal from $i \to j$ be denoted as $ij.$ Suppose that diagonals $ac$ and $bd$ intersect within the circle, where $a < b < c < d < n.$ Notice that, in order for $ac$ to be perpendicular to $bd$ , we must need $(b - a) + (d - c) = \frac{n}{2}$ by inscribed angle theorem. This can only be the case if $n$ is even, so if $n$ is odd, no diagonals may intersect within the circle. Then the optimal amount of diagonals is clearly $n - 3$ via triangulation.

Otherwise suppose that $n$ is even. Suppose that two diagonals $d_1$ and $d_2$ have the same orientation if they are parallel. I claim that, given a set of $2$ perpendicular diagonals, all other intersecting diagonals must have the same orientation as the first $2$ perpendicular diagonals.

Proof: Suppose that $ac$ and $bd$ intersect within the circle. This splits the circle into $4$ arcs. If we take diagonals $a'c'$ and $b'd'$ which intersect within the circle, assume for the sake of contradiction that $a'c' \not \perp bd$ or $a'c' \not \perp ac.$ WLOG $a'c' \not \perp bd.$ Now, $a'c'$ cannot intersect $bd$ , meaning that both $a'$ and $c'$ must lie on either major or minor arc $bd.$ Moreover, it must lie on either major or minor arc $ac$ , meaning that it is restricted to a quadrant of the region split by the diagonals. Moreover, since $b'd' \perp a'c'$ , we must need for $b'd'$ to not intersect either $ac$ or $bd.$ However, this implies that $a'c'$ and $b'd'$ intersect outside of the circle, contradiction.

Now, consider the following diagram:
$[asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.3) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -9.407683663103391, xmax = 12.75463264302359, ymin = -3.695196482299611, ymax = 8.868246462667162; /* image dimensions */ pen rvwvcq = rgb(0.08235294117647059,0.396078431372549,0.7529411764705882); pen hotpink = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); draw((-3.46,5.91)--(-4.66,4.41)--(-4.749142514811227,2.4911322056866125)--(-3.693378133618435,0.8863388945700068)--(-1.8959729659257687,0.20859656657824344)--(-0.043474694237122025,0.7167797553896964)--(1.156525305762878,2.2167797553896955)--(1.2456678205741056,4.135647549703084)--(0.1899034393813137,5.740440860819689)--(-1.6075017283113529,6.4181831888114536)--cycle, linewidth(0.5) + heavycyan); /* draw figures */ draw((-3.46,5.91)--(-4.66,4.41), linewidth(0.5) + heavycyan); draw((-4.66,4.41)--(-4.749142514811227,2.4911322056866125), linewidth(0.5) + heavycyan); draw((-4.749142514811227,2.4911322056866125)--(-3.693378133618435,0.8863388945700068), linewidth(0.5) + heavycyan); draw((-3.693378133618435,0.8863388945700068)--(-1.8959729659257687,0.20859656657824344), linewidth(0.5) + heavycyan); draw((-1.8959729659257687,0.20859656657824344)--(-0.043474694237122025,0.7167797553896964), linewidth(0.5) + heavycyan); draw((-0.043474694237122025,0.7167797553896964)--(1.156525305762878,2.2167797553896955), linewidth(0.5) + heavycyan); draw((1.156525305762878,2.2167797553896955)--(1.2456678205741056,4.135647549703084), linewidth(0.5) + heavycyan); draw((1.2456678205741056,4.135647549703084)--(0.1899034393813137,5.740440860819689), linewidth(0.5) + heavycyan); draw((0.1899034393813137,5.740440860819689)--(-1.6075017283113529,6.4181831888114536), linewidth(0.5) + heavycyan); draw((-1.6075017283113529,6.4181831888114536)--(-3.46,5.91), linewidth(0.5) + heavycyan); draw(circle((-1.7517373471185596,3.3133898776948465), 3.108141795106381), linewidth(0.5) + green); draw((-3.46,5.91)--(-3.693378133618435,0.8863388945700068), linewidth(0.5) + pink); draw((-4.749142514811227,2.4911322056866125)--(1.156525305762878,2.2167797553896955), linewidth(0.5) + pink); draw((-1.6075017283113529,6.4181831888114536)--(-1.8959729659257687,0.20859656657824344), linewidth(0.5) + pink); draw((0.1899034393813137,5.740440860819689)--(-0.043474694237122025,0.7167797553896964), linewidth(0.5) + pink); draw((-4.66,4.41)--(1.2456678205741056,4.135647549703084), linewidth(0.5) + pink); draw((-3.46,5.91)--(0.1899034393813137,5.740440860819689), linewidth(0.5) + pink); /* dots and labels */ dot((-3.46,5.91),dotstyle); label("$1$", (-3.6368467548196777,6.076370252674545), NE * labelscalefactor); dot((-4.66,4.41),dotstyle); label("$10$", (-4.946438172909,4.435783201441771), NE * labelscalefactor); dot((-4.749142514811227,2.4911322056866125),dotstyle); label("$9$", (-5.16230489017647,2.248333799798072), NE * labelscalefactor); dot((-3.693378133618435,0.8863388945700068),dotstyle); label("$8$", (-3.8814957010561444,0.5357911761428071), NE * labelscalefactor); dot((-1.8959729659257687,0.20859656657824344),dotstyle); label("$7$", (-1.9818685891024033,-0.05424451772161172), NE * labelscalefactor); dot((-0.043474694237122025,0.7167797553896964),dotstyle); label("$6$", (0.14801635460330687,0.42066226026682296), NE * labelscalefactor); dot((1.156525305762878,2.2167797553896955),dotstyle); label("$5$", (1.3424788568166441,2.0900315404685936), NE * labelscalefactor); dot((1.2456678205741056,4.135647549703084),dotstyle); label("$4$", (1.3568699713011423,4.104787568298317), NE * labelscalefactor); dot((0.1899034393813137,5.740440860819689),dotstyle); label("$3$", (0.24875415599479314,5.889285764376071), NE * labelscalefactor); dot((-1.6075017283113529,6.4181831888114536),dotstyle); label("$2$", (-1.550135154567462,6.5656681451474785), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy]$

If we have a total of $k$ diagonals, and $m$ vertices containing these diagonals. Notice that $m \ge k + 2$ , so at most $n - m = n - k - 2$ vertices contain no red diagonal. Thus there are at most $k + n - k - 2 = n - 2$ diagonals as requested.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

LTH-0-

31 posts

LTH-0-

#14 h Aug 27, 2020, 12:35 PM

Y by

Quite easy for a C5. Set all the perpendicular/parallel diagonals first, say that they divide the length of the circle in x subsets. Then the maximum number of diagonals able to be chosen in each subset of size k is
[k-1/2], which their sum is maximized when all k are odd.
From then on it’s simple calculating.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tigershark22

559 posts

tigershark22

#15 h Oct 7, 2020, 5:22 AM

Y by

Outline

This post has been edited 2 times. Last edited by tigershark22, Oct 7, 2020, 3:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fukano_2

492 posts

fukano_2

#16 h Nov 9, 2020, 2:11 AM

Y by

We claim the answer is $n-2$ for even $n$ and $n-3$ for odd $n.$ For simplicity, let the $n$ -gon be centered at the origin and symmetric across the $x$ and $y$ -axis and color all lines that are perpendicular to some other line blue and all lines that are not perpendicular to any other line red.

For odd $n,$ we cannot have any perpendicular lines, so taking a triangulation of the $n$ vertices gives that the maximum number of lines in the n-gon is $n-3$

Part 1: If $n = 4k$
Let $H$ be the number of lines that are perpendicular to some other line in the interior, and let $S$ be the number of lines that are not perpendicular to any other line in the interior. Then, a construction for the equality case is when all lines in the interior are perpendicular to some other line also in the interior. To prove that $n-2$ is maximal, notice that every time we add $k$ red lines, we must remove at least $k$ blue lines, so the number of lines in the interior are constant or decreasing as $S$ gets larger.

Part 2: If $n \equiv 2 \bmod 4$
We will use the definitions of $H$ and $S$ in part 1. Note that $H$ is maximized when all lines parallel and perpendicular to the $y$ -axis is drawn; let the polygon when H is maximized be called $\mathcal{P}$ . Similarly, $S$ is maximized when we take a triangulation of the $n$ -gon. Call the rectangle centered in the middle of the n-gon with two of its pairs of vertices spaced apart by 2 side lengths the $\textit{center rectangle}$ . Then, the construction is as follows: Consider $\mathcal{P}$ . Remove all blue lines except for the sides of the $\textit{center rectangle}$ , the line that passes through the circumcenter of the $\textit{center rectangle}$ and the line adjacently(?) parallel to one of the shorter sides of the $\textit{center rectangle}.$ Below is the construction for $n = 14$
$[asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(5); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -50.52218633629442, xmax = 76.562626678386, ymin = -42.81931672155241, ymax = 32.65205457619989; /* image dimensions */ draw((18.47703163272235,10.220904572353366)--(12.960893326923475,17.567960590407306)--(4.803256305735296,21.794066619799413)--(-4.380159371943386,22.062190531619457)--(-12.770465603946182,18.319227096807502)--(-18.705859340671847,11.306516128062103)--(-21.010763059734707,2.4130110379992153)--(-19.228662311785328,-6.599820418612106)--(-13.712524005986454,-13.946876436666045)--(-5.554886984798277,-18.17298246605815)--(3.6285286928804066,-18.441106377878203)--(12.018834924883205,-14.698142943066244)--(17.954228661608866,-7.685431974320846)--(20.25913238067173,1.2080731157420406)--cycle, linewidth(1) + blue); /* draw figures */ draw((18.47703163272235,10.220904572353366)--(12.960893326923475,17.567960590407306), linewidth(1) + blue); draw((12.960893326923475,17.567960590407306)--(4.803256305735296,21.794066619799413), linewidth(1) + blue); draw((4.803256305735296,21.794066619799413)--(-4.380159371943386,22.062190531619457), linewidth(1) + blue); draw((-4.380159371943386,22.062190531619457)--(-12.770465603946182,18.319227096807502), linewidth(1) + blue); draw((-12.770465603946182,18.319227096807502)--(-18.705859340671847,11.306516128062103), linewidth(1) + blue); draw((-18.705859340671847,11.306516128062103)--(-21.010763059734707,2.4130110379992153), linewidth(1) + blue); draw((-21.010763059734707,2.4130110379992153)--(-19.228662311785328,-6.599820418612106), linewidth(1) + blue); draw((-19.228662311785328,-6.599820418612106)--(-13.712524005986454,-13.946876436666045), linewidth(1) + blue); draw((-13.712524005986454,-13.946876436666045)--(-5.554886984798277,-18.17298246605815), linewidth(1) + blue); draw((-5.554886984798277,-18.17298246605815)--(3.6285286928804066,-18.441106377878203), linewidth(1) + blue); draw((3.6285286928804066,-18.441106377878203)--(12.018834924883205,-14.698142943066244), linewidth(1) + blue); draw((12.018834924883205,-14.698142943066244)--(17.954228661608866,-7.685431974320846), linewidth(1) + blue); draw((17.954228661608866,-7.685431974320846)--(20.25913238067173,1.2080731157420406), linewidth(1) + blue); draw((20.25913238067173,1.2080731157420406)--(18.47703163272235,10.220904572353366), linewidth(1) + blue); draw((12.960893326923475,17.567960590407306)--(12.018834924883205,-14.698142943066244), linewidth(1) + linetype("2 2") + blue); draw((-13.712524005986454,-13.946876436666045)--(12.018834924883205,-14.698142943066244), linewidth(1) + red); draw((-12.770465603946182,18.319227096807502)--(12.960893326923475,17.567960590407306), linewidth(1) + red); draw((18.47703163272235,10.220904572353366)--(-18.705859340671847,11.306516128062103), linewidth(1) + linetype("2 2") + blue); draw((20.25913238067173,1.2080731157420406)--(-21.010763059734707,2.4130110379992153), linewidth(1) + linetype("2 2") + blue); draw((-19.228662311785328,-6.599820418612106)--(17.954228661608866,-7.685431974320846), linewidth(1) + blue); draw((18.47703163272235,10.220904572353366)--(17.954228661608866,-7.685431974320846), linewidth(1) + linetype("2 2") + blue); draw((-18.705859340671847,11.306516128062103)--(-19.228662311785328,-6.599820418612106), linewidth(1) + linetype("2 2") + blue); draw((-18.705859340671847,11.306516128062103)--(12.960893326923475,17.567960590407306), linewidth(1) + red); draw((-12.770465603946182,18.319227096807502)--(4.803256305735296,21.794066619799413), linewidth(1) + red); draw((-19.228662311785328,-6.599820418612106)--(12.018834924883205,-14.698142943066244), linewidth(1) + red); draw((-13.712524005986454,-13.946876436666045)--(3.6285286928804066,-18.441106377878203), linewidth(1) + red); /* dots and labels */ dot((18.47703163272235,10.220904572353366),dotstyle); dot((12.960893326923475,17.567960590407306),dotstyle); dot((4.803256305735296,21.794066619799413),dotstyle); dot((-4.380159371943386,22.062190531619457),dotstyle); dot((-12.770465603946182,18.319227096807502),dotstyle); dot((-18.705859340671847,11.306516128062103),dotstyle); dot((-21.010763059734707,2.4130110379992153),dotstyle); dot((-19.228662311785328,-6.599820418612106),dotstyle); dot((-13.712524005986454,-13.946876436666045),dotstyle); dot((-5.554886984798277,-18.17298246605815),dotstyle); dot((3.6285286928804066,-18.441106377878203),dotstyle); dot((12.018834924883205,-14.698142943066244),dotstyle); dot((17.954228661608866,-7.685431974320846),dotstyle); dot((20.25913238067173,1.2080731157420406),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy]$
We now prove that $n-2$ is maximal. Note that if there were any more red lines, that would lessen the amount of lines in total. If the blue lines that pass through the space in between the red lines of length difference 1 are added back, then we would have to remove $k+1$ red lines and add $k$ blue lines, causing the overall number of lines to decrease.

This post has been edited 5 times. Last edited by fukano_2, Nov 9, 2020, 2:16 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kevinmathz

4680 posts

kevinmathz

#17 h Nov 22, 2020, 4:43 PM

Y by

Lets look at the case if $n$ is odd. Here, we have that we let $O$ be the circumcenter of the $n$ -gon. Now, if $n=3$ our answer is obviously $0$ ; Otherwise, consider a convex quadrilateral $ABCD$ whose sides are on the $n-gon$ . We see that $AC$ meets $BD$ at a right angle if and only if $\angle ACD + \angle BDC = 90^{\circ}$ which means $\angle AOD + \angle BOC = 180^{\circ}$ . However, two arcs cannot sum up to a $180^{\circ}$ arc if $n$ is odd, because if they can, then that means an even number of arcs sum up to $360^{\circ}$ . Now if $n$ is odd, we have that two lines cannot intersect each other in the interior of the polygon, meaning that because a diagonal is in the interior of the polygon, we see we can draw a diagonal taking one vertex to another two spots away. This means that each additional diagonal takes away one or two points; thus, because we already have three spots taken by a diagonal and with one spot remaining it is impossible to draw a diagonal, the number of diagonals we have is going to be at most $1+\frac{(n-1-3)}{1}=n-3$ if $n$ is odd.

Now we check the case if $n$ is even. Consider a convex quadrilateral $ABCD$ whose sides are on the $n$ -gon. Then, if $AC \perp BD$ , that means that if minor arc $AB$ is the largest arc of the cyclic quadrilateral, since $\angle ACB + \angle DBC = 90^{\circ}$ , then $\angle ACB < 90^{\circ}$ meaning arc $AB$ is less than $180$ degrees. As a result of this, we cannot have two perpendicular intersections by four lines all of different angles. So, if we let two chosen lines $AC$ and $BD$ be perpendicular, this means that if we make another perpendicular line, it takes up one or two more points, similar with non-perpendicular lines. Now, we see that the perpendicularity condition allows us to make up to one more line than before, so our answer is the maximum number of diagonals possible is $\boxed{2\left\lfloor\frac n2 \right\rfloor-2}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rcorreaa

238 posts

rcorreaa

#18 h Nov 26, 2020, 4:13 AM

Y by

The answer is $n-3$ if $n$ is odd and $n-2$ if $n$ is even. Indeed, if $n$ is odd, there aren't perpendicular diagonals, so the best we can do is triangularize the polygon. This gives us at most $(n-3)$ diagonals, as desired (for the example, just triangulate the polygon).

Now, suppose that $n$ is even. Let $a_n$ the answer. $a_n \geq n-2$ by triangularizing the whole polygon around one single vertex $v$ and adding one edge between the $\frac{n-2}{2},\frac{n+2}{2}$ vertices after $v$ in the clockwise.

Then, we prove the upper bound.

Take a pair of perpendicular diagonals (they exist, otherwise the best we could do was a triangularization, but we already have an example for $n-2$ ). Call it $D_1,D_2$ .

Now, take the two most smaller drawn diagonals $d_{1,a};d_{1,b}$ that are parallel to $D_1$ . Define $d_{2,a};d_{2,b}$ similarly.

Suppose that $d_{1,a}$ and $d_{2,a}$ have endpoints $A_1,A_2$ and $A_3,A_4$ , respectively. Define $B_1,B_2,B_3,B_4$ similarly. Suppose that these points are placed in the order $A_1,A_3,B_1,B_3,A_4,A_2,B_4,B_2$ clockwise.

Pick a region between two consecutive points $(A_i,B_j)$ , $(A_i,A_j)$ or $(B_i,B_j)$ , and suppose that there are $k$ points between them. Among these $\binom{k+2}{2}$ possible diagonals, we cannot have any $2$ drawn diagonals intersecting each other, because since none of them are parallel to $D_{1,a};D_{1,b};D_{2,a};D_{2,b}$ (due to the minimal length) $(\spadesuit)$ , this would implie that we would have a diagonal intersecting one of $D_{1,a};D_{1,b};D_{2,a};D_{2,b}$ , and not perpendicular to it, a contradiction.

Hence, the best we can do in this region is to triangulate it, using $k$ edges. $\qquad (\star)$

Since the circle was splitted into $2l \leq 8$ regions $R_1,R_2,...,R_{2l}$ with an amount of $r_1,r_2,...,r_{2l}$ points in it, respectively:

$\implies$ from $(\star)$ , $r_1+r_2+...+r_{2l}=n-2l \geq$ #[Amount of diagonals among the regions] $\qquad (\star \star)$

Since we also cannot have a diagonal connecting $2$ distinct reguins (due to $(\spadesuit)$ and also because if it was possible, we could erase it and add one diagonal in each region, increasing the number of diagonals, a contradiction when we take the maximal example).

Thus, from $(\star \star)$ , the number of diagonals is at most $n-2l+l=n-l$ , and since $l \geq 2$ , we can have at most $(n-2)$ diagonals, as desired.

$\blacksquare$

This post has been edited 2 times. Last edited by rcorreaa, Nov 26, 2020, 5:56 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L567

1184 posts

L567

#19 h Sep 1, 2021, 6:22 AM

Y by

Nice problem!, although I overcomplicated it quite a bit

For odd $n$ , there are no perpendicular diagonals, so the best is $n-3$ by triangulating the figure.

For even $n$ , first I will show that every intersecting diagonal has to have the same orientation (mod $90^\circ$ ). If $AC \perp BD$ , say the span of this pair is the measure of arc $ABCD$ . Note that each pair must span $> 180^\circ$ . So, if there is another pair of perpendicular diagonals, then since those span $> 180^\circ$ too, they must intersect this pair and hence must be perpendicular to this.

Now, suppose some configuration of diagonals achieves the maximum and draw all the perpendicular diagonals. They divide the arc into many subparts, call each a region. If a region has $k$ vertices, then see that it can have at most $k$ diagonals in it (by triangulating). But also note that this is possible only when the diagonal connecting the border vertices has not been drawn yet.

Call a diagonal sad if it is not part of a rectangle(say $s$ of them) and call a region bad if it does not have as many diagonals in it as vertices (Say there are $b$ of them). Also, say there are $z$ rectangles. I will now count the number of diagonals.

The number of perpendicular diagonals are $2z+s$ . See that the number of vertices part of a perpendicular diagonal is exactly $4z+2s$ , so there are $n-4z-2s$ vertices not part of a perpendicular diagonal. Now, each region has as many diagonals as vertices except for bad regions, so the diagonals among the regions are $n-4z-2s-b$ . So, the total diagonals is at most $(4z+s)+(n-4z-2s-b) = n-s-b$ .

Claim: $b+s \ge 2$

Proof: Orient the polygon so that the perpendicular diagonals are parallel to the $x$ and $y$ axes and consider the rectangle with the topmost side (which also has the lowermost side). And consider the region above the topmost side and below the lowermost side. Either there is a sad diagonal connecting the top and the bottom, or the region is bad. So either way, there is a contribution of at least $1$ to $b+s$ . Similarly considering the leftmost and rightmost side, we see that again there is a sad diagonal or bad region, so $b+s \ge 2$ , as claimed. $\square$

So, we have proved that there are at most $n-2$ diagonals. For a construction, call the vertices $A_1, A_2, ..., A_{2m}$ . Draw the diagonals $A_1A_3, A_1A_4, \cdots A_1A_{2m-1}$ and the diagonal $A_mA_{m+2}$ , which works (There are many other possible equality cases though), so we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

guptaamitu1

656 posts

guptaamitu1

#20 h Sep 8, 2021, 11:34 AM

Y by

A different Solution: (though, the main ideas are same)

The answer is $n-3$ for odd $n$ and $n-2$ for even $n$ .

Construction: Suppose $V_1,V_2,\ldots,V_n$ are the $n$ vertices in that order. Consider all the $n-3$ diagonals passing through $V_1$ . If $n$ is odd, then we are just done and if $n$ is even, add one more diagonal $\overline{V_{\frac{n}{2}}V_{\frac{n}{2} + 2}}$ .

Proving our upper bounds are indeed the most optimal:
The case when $n$ is odd is easy as there are no perpendicular diagonals and it is not hard to see that any partition into non-intersecting diagonals can have at most $n-3$ diagonals.
Now assume $n$ is even and let $\mathcal P$ be our polygon. We color a diagonal red if it intersects some other diagonal. If no diagonal is red, then we are done. So assume $d_1,d_2$ are two intersecting red diagonals. Observe that $d_1,d_2$ partition $\mathcal P$ into four regions, each of which does not contain a diameter of $\mathcal P$ . So any other diagonal intersecting $d_1$ or $d_2$ must be perpendicular to them. Now let $d_1(\text{max})$ be the diagonal of maximum length parallel to $d_1$ and define $d_2(\text{max})$ similarly. Now, let $X,Y$ be the set of all red diagonals which are parallel to $d_2,d_1$ , respectively and $Z$ be the set of the non-red diagonals. Let $x,y,z$ be the respective cardinalities. We want to prove $x+y+z \le n-2$ . So it suffices to show $\boxed{x+z \le (n-2)-x ~ \text{and} ~ y+z \le (n-2)-y}$ Now it is enough to show $x+z \le 2(n-2) - x$ (as the other part follows analogously).
It is not hard to prove that any diagonal in $X$ must intersect $d_1(\text{max})$ in the interior of $\mathcal P$ . Now the $x$ diagonals in $X$ along with $d_1(\text{max})$ divide $\mathcal P$ into $2(x+1)$ arcs. Note that any diagonal of $Z$ must have both it endpoints in some arc. Now it is easy to note that any arc containing $t$ points can give at most $t-2$ non-intersecting diagonals. So it not hard to obtain that $z \le n - 2(x+1)$ .
This completes the proof of the problem. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

squareman

966 posts

squareman

#21 h Mar 1, 2022, 10:44 PM • 1 Y

Y by Catsaway

Nice problem!

The answer is $n-3$ for odd $n$ and $n-2$ for even $n$ . For odd $n,$ no two diagonals can be perpendicular to each other so the best we can do is to triangulate the polygon, yielding $n-3.$

For even $n,$ note that if two selected perpendicular diagonals intersect, any other two selected perpendicular intersecting diagonals must be oriented in the same way. Consider the set $S$ of selected diagonals where a diagonal is in $S$ iff it intersects some other selected diagonal. The longest diagonal in either direction must not share an endpoint with any other diagonal in $S,$ because then that diagonal would have to intersect an even longer diagonal.

This implies that there are at least $|S|+2$ points that are an endpoint of a diagonal in $S.$ Any other selected diagonal not in $S$ must be "contained within" some arc bounded by points that are endpoints of some diagonals in $S.$ The maximum number of nonintersecting diagonals we can fit in each one of these arcs is the number of points that lie (strictly) between the two endpoints. If we sum this number over all arcs we will get $n - |S|-2$ points, and thus a maximum of $n-|S|-2$ diagonals not in $S,$ and so at most $n-|S|-2+|S| = n-2$ in total.

A valid construction for a $2n$ -gon $A_1A_2 \dots A_{2n}$ would be choosing the diameter $A_1A_n,$ then $A_2A_{2n}$ (perpendicular to the diameter), then join $A_2$ to all the vertices on its side of the diameter ( $n-2$ in total), and similarly for $A_{2n}$ ( $n-2$ as well). $2+2(n-2) = 2n-2$ so it works. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1673 posts

awesomeming327.

#22 h Aug 14, 2022, 4:24 AM • 2 Y

Y by RoyalCactus, dolphinday

We claim that the answer is $f(n)=n-2$ when $n$ is even and $f(n)=n-3$ when $n$ is odd. For $n$ odd just take all diagonals protruding from one vertex. There are no intersections on the inside.

$~$
For $n$ even take all the diagonals protruding from one vertex and an additional one which connects the two vertices adjacent to the antipode of the vertex we chose before.

$~$
The bound holds for odd $n$ because no two diagonals are perpendicular, so there are no intersections in the middle. Thus, the maximum number of edges is reached during a complete triangulation.

$~$
Now let's prove the bound for even $n$ . Put the regular $n$ -gon on a circle and consider two intersecting diagonals, $AB$ and $CD$ . Since they intersect inside the circle, major arc $AC$ contains $B$ and $D.$ Thus, any point which intersects the major arc $AC$ will intersect either $AB$ or $CD$ and therefore must be parallel to one of them.

$~$
In particular, if there are two other intersection diagonals, neither of them $AB$ or $CD$ , then one of them will be parallel to either $AB$ or $CD$ . Thus, the other one will follow the same rule. Generally, this means that any diagonal which intersects another will have one of two directions, lets call them vertical and horizontal.

$~$
Of those diagonals, suppose $a$ are vertical and $b$ are horizontal, then the circumference of this circle is divided into $2a+2b$ arcs. Let the interior of these arcs have $a_1,a_2,\dots,a_{2a+2b}$ points. If an arc has $k$ points then we can draw at most one more point in this arc. Thus, if we join all of them then the maximal number of diagonals is $n-(2a+2b)+(a+b)=n-(a+b)\le n-2$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JAnatolGT_00

559 posts

JAnatolGT_00

#23 h Dec 25, 2022, 6:22 PM

Y by

We claim the answer $n-3$ for odd $n$ and $n-2$ for even $n.$

The construction. Denote the vertices of polygons as $A_1,A_2,\dots,A_n$ anticlockwise. For odd $n$ we just select all diagonals $A_1A_i$ for $i=3,4,\dots,n-2.$ For even $n=2k$ we also select segment $A_kA_{k+2}$ , which intersect only diagonal $A_1A_{k+1}.$

The upper bound. By the parity argument, there are no perpendicular diagonals for odd $n,$ so by trivial induction we can select at most $n-3$ segments (each doesn't intersect others in the interior).

For even $n$ we paint red every selected diagonal, which intersects some other selected segment; define $m$ as a number of red segments. Pair of intersecting red diagonals $d_1,d_2$ are perpendicular, and moreover - they divide the circumscribed circle of polygon on four arcs, none of which contains two antipodal points. Therefore we conclude that all red segments are parallel to one of $d_1,d_2.$ Next, the longest of red segments on each direction hasn't any common endpoint with other red diagonals, so the set of such endpoints has a cardinality at least $m+2.$ Finally divide the circle on disjoint arcs by endpoints of red segments; if arc contains $l$ vertices of polygon in the interior, then the respective segment contains at most $l$ selected diagonals - paint all such segments blue. But it's obvious, that all selected diagonals are either red or blue, and so there are at most $m+n-(m+2)=n-2$ of them as desired.

This post has been edited 2 times. Last edited by JAnatolGT_00, Dec 25, 2022, 6:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#24 h Mar 11, 2023, 4:03 PM

Y by

Cool problem!

The answer is $n-3$ for $n$ odd and $n-2$ for $n$ even. Notice that the $n$ odd case is tautological as no diagonals can be perpendicular.

Call a drawn diagonal interesting if it intersects some other drawn diagonal in the interior of the $n$ -agon.

Claim. [Housekeeping] Every pair of interesting diagonals consists of two diagonals that are parallel or perpendicular to each other.

Proof. Suppose there exist two interesting diagonals that do not satisfy the condition, say $d_1$ and $d_2$ . Let $\ell_1 \perp d_1$ and $\ell_2 \perp d_2$ be diagonals which we know exist by definition. The condition means that $\ell_1 \cup d_1$ and $\ell_2 \cup d_2$ are disjoint; but this obviously cannot happen as it means that $\ell_2 \cup d_2$ is contained in a less than $180^\circ$ arc-section of the $n$ -gon. $\blacksquare$

Now, notice that the interesting diagonals partition the $n$ -gon into some number of continuous sections of points on which no point except for the endpoints is an endpoint of an interesting diagonal. We will call these sections blobs.

Let there be $\ell$ points which are an endpoint of an interesting diagonal, and thus $\ell$ blobs. Observe that in any blob with $n$ points, we can draw at most $n-2$ non-interesting (and thus non-intersecting) diagonals. This means that the number of non-interesting diagonals (which we will denote by $k$ ) is upper bounded by $k \leq \sum_{B \text{ blob}} |B| - 2 = (n+\ell) - 2\ell = n - \ell.$ To finish, we have the following claim:

Claim. There exists at least two endpoints with exactly one interesting diagonal emanating from them, unless the interesting diagonals form precisely a union of rectangles.

Proof. By the previous claim, this means that any endpoint with at least two interesting diagonals passing through them harbors exactly two interesting diagonals that intersect perpendicularly. On the other hand, this means that the interesting diagonals must form unions of rectangles, as needed. $\blacksquare$

Thus, when not in the rectangular case, the number $i$ of interesting diagonals is at most $\ell - 2$ by double counting, so $k + i \leq n-2$ , as needed. If we in the rectangular case, observe that there exists a pair of sides of one of the rectangles that intersects no other diagonals in its interior. Thus, for those two blobs bounded by the $n$ -gon and one of these two diagonals, the bound is $n-3$ instead of $n-2$ ; thus, we have $k \leq n - \ell - 2$ and $i \leq \ell$ , which yields the conclusion. For a construction for $n$ even, make all diagonals interesting by drawing all $\frac{n-2}2$ parallel diagonals in one direction and the corresponding $\frac{n-2}2$ parallel diagonals in a direction perpendicular to that direction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sman96

136 posts

sman96

#25 h May 2, 2023, 12:10 PM

Y by

First, if no two diagonal intersects in the interior of the polygon then, at most we can draw diagonals that ar required for a triangulation which is $n-3$ .
Now, if $n$ is odd then, we can't have two diagonals perpendicular to each other. so the answer will be $n-3$ .
Now for $n$ even we will show that the answer is at most $n-2$ .
First, if no two diagonals intersects then we can draw at most $n-3$ of them which is clearly not the maximum.
Now we label the vertices by $1,2,\dots, 2k$ in clockwise order. Let, $(x, y)$ means the diagonal between $x$ and $y$ in the polygon.

So assume that two diagonals $d_1=(a,b)$ and $d_2 = (c, d)$ are perpendicular to each other where $a < c < b < d$ .
Then clearly, $d(a, c) + d(b, d) = d(c,b) + d(d,a) = n/2 = k$ because of the perpendicular property.
Let, $d(x, y)$ be the clockwise distance from $x$ to $y$ in the polygon.

\textbf{Claim:} If any other two diagonals $e_1 = (x, y)$ and $e_2 = (z, w)$ where $x < z < y < w$ intersects then they also intersects with $d_1$ or $d_2$ .
\underline{Proof:} If they don't then, they must all lie on one of the minor arc $(a,c), (c,b), (b,d), (d,a)$ but all of them have length strictly less than $k$ .
But then $d(x, z) + d(y,w) < k$ therefore they aren't perpendicular which is a contradiction. $\square$

So, all the diagonals that intersects with some other diagonal are all connected [if we consider a graph].
And we can partition them into two groups one $G_1$ with all diagonals parallel with $d_1$ and other $G_2$ with all diagonals parallel with $d_2$ .
Now, let there are a total of $m$ diagonals of them. Then, let all of their endpoints be, $x_1, x_2, \dots, x_{2m}$ in increasing order and define $x_{2m+1} = x_1$ and similar.
Now notice that for any other diagonal their both endpoints must lie between $x_i$ and $x_{i+1}$ for some $i$ .
Now, for each minor arc $(x_i, x_{i+1})$ we can add at most $d(x_i, x_{i+1}) - 1$ diagonals between them by using triangulation as there can't be any intersections [Here we assumed that $m > 1$ so diagonal $(x_i, x_i+1)$ can't be already drawn].
So we can add at most $\displaystyle \sum_{i=1}^{2m} d(x_i, x_{i+1}) - 1 = 2k - 2m$ diagonals.
So in total we get at most $2k - 2m + m = n-m$ diagonals.
And, $m > 1$ as we assumed at least one intersection. So, $n-m \leq n-2$ .
And, we can draw $n-2$ diagonals like this,

So the answer is $n-2$ for even $n$ and $n-3$ for odd $n$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

YaoAOPS

1497 posts

YaoAOPS

#26 h Jun 20, 2023, 6:57 AM

Y by

If $n$ is odd, then no diagonals can intersect, so there are at most $n - 3$ which occurs with constructing all diagonals to one point. This is optimal due to triangulations.
If $n$ is even, then we can construct an additional diagonal on the points next to the opposite point to get $n - 2$ diagonals.
Let $T$ be the set of diagonals that intersect another. Then, since diagonals in $T$ must come with a perpendicular one, it follows that all diagonals in $T$ are mutually parallel or perpendicular.
The two longest diagonals in $T$ can not share an endpoint with other diagonals in $T$ , or else that leads to a contradiction of maximality.
As such, there are at most $n - (k + 2)$ remaining points that are not endpoints of red diagonals. Inductively it follows that on an arc with $c$ points in between the red diagonal end points, there is at most $c$ diagonals not in $T$ . This gives the bound of $n - (k + 2) + k = n - 2.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5000 posts

IAmTheHazard

#27 h Aug 26, 2023, 2:59 PM • 1 Y

Y by centslordm

The answer is $n-3$ when $n$ is odd and $n-2$ when $n$ is even.

If $n$ is odd, then no diagonals can be perpendicular (use complex numbers), so the diagonals must dissect the $n$ -gon into polygons, so the maximum is $n-3$ achieved with a triangulation.

Now suppose that $n$ is even, and let $\mathcal{P}$ be the polygon. Label the vertices $A_1,\ldots,A_n$ , and draw every edge from $A_1$ , as well as $\overline{A_2A_n}$ , which is a construction for $n-2$ . We now show that it is maximal.

Consider every diagonal which intersects some other diagonal inside $\mathcal{P}$ ; I claim that they must all be parallel or perpendicular to some fixed line. Indeed, pick two perpendicular diagonals intersecting inside $\mathcal{P}$ , which divide the interior of the polygon into four regions. Then if some perpendicular diagonals not parallel or perpendicular to these two diagonals intersect in the interior of $\mathcal{P}$ , it must be in one of these regions, but it's easy to see that the diagonals intersect the boundary of the region containing their intersection point: contradiction.

Therefore consider every diagonal parallel or perpendicular to this fixed line and call such diagonals blobby. Inscribe $\mathcal{P}$ in a circle, and consider the regions bounded by the circumference of the circle and these diagonals. For any region that contains two straight edges and $v$ vertices on the circumference but not the straight edges, we can draw at most $v$ vertices inside its interior, and for any region that contains one straight edges and $v$ vertices on the circumference but not the straight edge, we can draw at most $v-1$ vertices inside its interior.

If there are $k$ blobby diagonals, the circumference is divided into regions collectively containing at most $n-k$ vertices that don't lie on diagonals, hence we immediately get that there are at most $n$ diagonals total. We now dispel the possibility of $n$ or $n-1$ diagonals by examining equality cases:

If there are $n$ diagonals, then every vertex on a blobby diagonal lies on two blobby diagonals, which clearly implies that the blobby diagonals form "rectangles". Furthermore, we need every region to contain two straight edges, but this fails by considering the "skinniest" rectangle.
If there are $n-1$ diagonals, and every vertex lies on two blobby diagonals (hence they form "rectangles"), then at most one region contains exactly one straight edge, but this fails for the same reason.
Otherwise, if there are $n-1$ diagonals, then the blobby diagonals all form "rectangles" with the exception of one "connected component", which is a path, and every region contains two straight edges. If there are no rectangles at all then this clearly cannot happen. Otherwise, superimpose the natural "completion" of this connected component to a rectangle (by taking the vertices contained within it and drawing perpendicular edges until we get a rectangle). Either the "skinniest" or "fattest" rectangle is not superimposed (i.e. actually exists), so for the same reason as before we can still find some region containing one straight edge.

This eliminates all possibilities, so we must have at most $n-2$ diagonals in total. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7586 posts

asdf334

#28 h Nov 19, 2023, 9:31 PM

Y by

First note that all perpendicular diagonals must be oriented in two directions. To see this, suppose otherwise. If two pairs of perpendicular diagonals don't intersect, then one pair must be entirely contained within one of the four "regions" of the other pair. As a consequence the region must have at least half the vertices of the $n$ -gon (angle chase!) which can't happen.

Suppose there are $h$ horizontal and $v$ vertical intersecting diagonals. These split the polygon into $2(h+v)$ regions (it's a bit annoying to prove that the regions are separated from each other so I'll ignore). By trivial induction a region of size $s$ (meaning it has $s$ vertices not including endpoints, excuse the weird definition) can contribute $s$ extra edges.

So the sum of all regions' sizes plus $h+v$ should be the maximum count. This is precisely $n-h-v$ .

But wait! We assumed $h$ and $v$ were positive. For $n$ even we can set $h=v=1$ and find a trivial construction for $n-2$ . For $n$ odd we can never have perpendicular diagonals, so $h=v=0$ and we resort to any triangulation giving $n-3$ . Done!

(my writing sucks._)

This post has been edited 1 time. Last edited by asdf334, Nov 19, 2023, 9:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#29 h Dec 22, 2023, 8:56 PM

Y by

The answer is $\boxed{n-2}$ if $n$ is even and $\boxed{n-3}$ otherwise.

First, consider if $n$ is odd: None of the diagonals can be perpendicular, so the optimal diagonals will just be a triangulation of the polygon, resulting in $n-3$ diagonals.

If $n$ is even, the optimal configuration of a polygon $\mathcal{P}$ is as follows: Take a point $A$ and its antipode $B$ w.r.t. the circumcircle of $\mathcal{P}$ . Draw all diagonals with point $A$ in it, and then the diagonal connecting the adjacent points to $B$ on either side. This results in $n-2$ diagonals in total.

To see that this is the maximum, we denote a diagonal as intersecting if the diagonal intersects with another diagonal.

Claim: All intersecting diagonals are either parallel or perpendicular to a fixed line $\ell$ .

Proof: Take a pair of intersecting diagonals and set one of them to be $\ell$ . This pair splits the polygon into $4$ sections, so FTSOC let there be another pair of intersecting diagonals that are not properly oriented to $\ell$ . It is clear they must lie completely in one of the regions, but a simple angle chase yields that the region they are contained in must have at least $\tfrac{n}{2}$ points, an impossibility. Hence, all intersecting diagonals are either parallel or perpendicular to a fixed line $\ell$ .

Denote an intersecting diagonal as rectangular if it forms a rectangle with three other intersecting diagonals, denote a point as red if it lies on a rectangular diagonal, and denote the point as blue otherwise. In order to maximize the number of diagonals, we need to minimize the number of red points, as each blue point accounts for $1$ more diagonal.

Let there be $k$ intersecting diagonals. It is clear that the largest intersecting diagonal of each orientation cannot be rectangular, and they account for $4$ red points. To minimize the number of red points, every other intersecting diagonal needs to be rectangular, which accounts for $k-2$ points.

Hence, the number of blue points is at most $n-4-(k-2)=n-k-2$ , which means the maximal number of diagonals is

$(n-k-2)+k = n-2.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

thdnder

194 posts

thdnder

#31 h Jan 22, 2024, 7:01 AM

Y by

Answer: $n-3$ , if $n$ is odd and $n-2$ , if $n$ is even.

First consider the case $n$ is odd. Then no two diagonals can be perpendicular, so it suffices to prove that we can select at most $n-3$ diagonals. In the maximal case, these diagonals should divide the $n$ -gon into $n-2$ triangles, so we can select at most $n-3$ diagonals. Construction is obvious.

Now consider the case $n$ is even. If no two diagonal are intersect each other, the proof of odd case works. Suppose there are two perpendicular diagonals are selected. Call them $k, l$ .

Claim: If the diagonals $x, y$ are selected and perpendicular to each other, then $x$ is either parallel to $k$ or $l$ .

Proof. Let $P = x \cap y$ . If $P$ lies on either $k$ or $l$ , then $x$ is either perpendicular to $k$ or $l$ . Hence we can assume $P$ doesn't lie on $k$ and $l$ . Thus the points $x \cap k$ , $x \cap l$ cannot lie inside of the polygon. Similarly $y \cap k, y \cap l$ cannot lie inside of the polygon. Therefore $x, y$ lie on one side of $k$ (and $l$ ), so the angle between $x, y$ is greater than $90^{\circ}$ , a contradiction. $\blacksquare$

Color black any diagonal that intersects another diagonal inside of the polygon. Let $k$ be the number of the black diagonals. It's clear that the longest diagonal of each direction are not the sides of a black rectangle. Hence there are at least $k+2$ points that are incident to some black diagonal, which means there are most most $n-k-2$ points that are not incident to the black diagonal. Thus there are at most $n-k-2$ diagonals which are not black and adding the black diagonals, we get there are at most $n-k-2+k = n-2$ diagonals, as required. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

666 posts

Shreyasharma

#32 h Feb 5, 2024, 2:01 AM

Y by

The answers are $\boxed{n-2}$ and $\boxed{n-3}$ for even and odd $n$ respectively. Constructions have already been presented above, just consider triangulating. For even $n$ , simply add one minimal perpendicular diagonal.

Begin with $n$ even. Consider drawing in all diagonals that intersect some other diagonal inside the $n$ -gon. Note that we should only have $2$ ``classes" of lines at the end of this process, say vertical lines and horizontal lines. It is easy to see that given two diagonals, one horizontal and the other vertical, they must intersect within the $n$ -gon.

Now say we draw $m$ such diagonals and call them special. All other diagonals are boring. For each vertex $v_i$ give it a counter $c_i$ for the number of diagonals emitting from said vertex. Then observe that the $m$ diagonals divide the $n$ -gon into distinct convex regions that have no special diagonals in their interior. Call a region internal if it contains at most $1$ vertex of the $n$ -gon and external otherwise.

Claim: Boring diagonals exist only in external regions.
Proof. Note that no boring diagonals may intersect an internal region, as this contradicts the perpendicularity criteria. Thus boring diagonals may only exist in external regions. Moreover each boring diagonal is contained within a single external region. $\square$

Finally in all external regions we find that the maximal number of boring diagonals is simply the number of points that lie strictly between the two endpoints on the $n$ -gon. Thus say we draw $m$ special diagonals.

Claim: There are at most $n - m - 2$ boring diagonals.
Proof. Begin by noting that the longest diagonals in each class, either vertical or horizontal, do not share endpoints with any other diagonals. Now let $S$ denote the set of vertices that do not lie on a special segment. It is clear,
$\begin{align*} (\# \text{ boring}) = n - |S| \end{align*}$ Hence we will now attempt to minimize $|S|$ . To minimize make groups of $4$ diagonals. In each of these groups, let the $4$ diagonals form a rectangle so that we use at most $4$ points for any group. Recall that we may do this for all diagonals, except for the longest horizontal and vertical diagonals. Thus we have a bound of at least $m + 2$ vertices used in special diagonals. Subtracting we have a total of $n - (m + 2)$ boring diagonals, proving our claim. $\square$

Then,
$\begin{align*} (\# \text{ diagonals}) &= (\# \text{ boring}) + (\# \text{ special})\\ &\leq (n - m - 2) + (m)\\ &= n - 2 \end{align*}$ proving our original claim.

For odd $n$ we cannot have perpendicular diagonals, thus proving our claim upon triangulation. $\square$

This post has been edited 1 time. Last edited by Shreyasharma, Feb 5, 2024, 2:02 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1727 posts

OronSH

#34 h Jul 26, 2024, 9:08 AM

Y by

The answer is $n-3$ if $n$ is odd and $n-2$ if $n$ is even. If $n$ is odd then no two diagonals are perpendicular and triangulation is maximal (otherwise there is some non-triangle that we can split).

If $n$ is even, one such construction is to pick a vertex and draw all diagonals from it, then take the two vertices second-farthest from it and draw the diagonal between them.

To do this, first notice that any two pairs of perpendicular intersecting diagonals must intersect (e.g. each splits the circumcircle into halves, two of each of the halves must intersect, then zoom in at where they intersect). Thus all intersecting diagonals must have one of two perpendicular orientations.

Now consider all lines that intersect another line in the interior of the polygon. Suppose there are $k$ lines. These lines cut up the circumcircle into $r$ arcs. Suppose one of these arcs has $m$ vertices of the polygon, counting endpoints of the arc. Then it has at most $m-2$ diagonals within it, e.g. since the diagonals are at most a triangulation of the $m$ vertices plus one additional point. Summing this across all arcs, we get $n+r-2r=n-r$ of these diagonals, since no nonintersecting diagonal can have endpoints in two different arcs, and the $+r$ is because the $m$ sum to $n+r$ since each arc endpoint is counted twice. Adding back the $k$ lines, we get $n-r+k$ diagonals.

Now let $p$ be the number of right angles at a polygon vertex formed by two of these $k$ lines. We can see that $r=2k-p$ for example by induction. Now we claim $k-p\ge 2$ which would finish after rearranging. To do this, first consider the shortest line of one orientation. Then the line that intersects it cannot form right angles on the circumcircle, and similarly for the other orientation, so we have found $2$ lines without right angles at polygon vertices. Then all other lines are either parts of rectangles which give $k-p=0$ or broken lines with $k-p=1$ so summing these we finish.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ihatemath123

3440 posts

ihatemath123

#35 h Jan 9, 2025, 6:14 PM

Y by

The answer is $n-3$ when $n$ is odd and $n-2$ when $n$ is even. For odd $n$ , regular $n$ -gons don't have perpendicular diagonals (each diagonal is adjacent to one side, and no two sides are perpendicular), so no two diagonals can intersect. So, at best, we can triangulate the polygon, which is $n-3$ diagonals.

For even $n$ , we can attain $n-2$ diagonals by drawing every diagonal coming out of a vertex $P$ , and then drawing the diagonal connecting the two points adjacent to the antipode of $P$ . We now show that $n-2$ is optimal.

Claim: In a valid selection of diagonals, all pairs of intersecting/perpendicular diagonals have the same orientation.
Proof: It suffices to show that any two pairs of intersecting diagonals intersect each other (i.e. they bound a rectangle). It's easy to see that given any pair of intersecting/perpendicular diagonals, the sum of the minor arcs of the diagonals is more than $180^{\circ}$ . So, given two pairs of intersecting diagonals, there must be one minor arc from the first pair that intersects the first minor arc from the second pair, meaning those two diagonals intersect.

In a valid set of polynomials, call a diagonal a "rib" if it intersects another diagonal, and "residual" otherwise. All ribs must be horizontal or vertical, and these diagonals partition the polygon's perimeter into some arcs. No residual diagonals may cross between two arcs, and we can triangulate each arc at best. So, in an arc of length $k$ , we can draw in $k-1$ residual diagonals.

Call a vertex "coincidential" if two ribs meet at the vertex, and let $C$ be the number of such vertices. If $R$ is the total number of ribs, there are $2R - C$ arcs, so we can draw at most $n - (2R - C)$ residual diagonals. So, it suffices to show that $C \leq R-2$ .

Each rib could be the end of up to two coincidential vertices, and each coincidential vertex connects two ribs. So, we just need to identify four vertices that are the endpoint of exactly one rib. Consider the highest horizontal rib; since a vertical rib intersects it, the top endpoint of this vertical rib, by assumption, only connects to this vertical rib. Similarly, there is such an endpoint underneath the lowest horizontal rib , an endpoint to the right of the rightmost vertical rib and an endpoint to the left of the leftmost vertical rib. Thus, $C \leq R-2$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

792 posts

shendrew7

#36 h Jan 15, 2025, 6:48 PM

Y by

Our answer is
$\begin{cases} n-2 & \quad n \equiv 0 \pmod 2 \\ n-3 & \quad n \equiv 1 \pmod 2. \end{cases}$
We can construct $n$ odd using the $n-3$ diagonals from one vertex, and $n$ even similarily but adding the furthest chord from our vertex perpendicular to the drawn diameter. Notice there are no perpendicular diagonals when $n$ is odd, so no diagonals can intersect internally, and thus induction just gives our desired answer. We now focus on $n$ even.

Define the \emph{diagonal web} to be the set of diagonals which internally intersect another diagonal. We first show that every diagonal in this web has one of two perpendicular orientations; indeed, the arc that each pair of perpendicular diagonals inscribes is greater than 180 degrees, so we can't have two disjoint pairs.

Next, observe that a diagonal of maximum length in each direction cannot be part of a rectangle in the web, since the other two sides in the rectangle would not be part of the web. Thus if we have $w$ diagonals in our web, at least $w+2$ vertices are incident on some diagonal in our web, so at most $n-w-2$ are not.

We now consider the diagonals which do not internally intersect. Our web cuts our $n$ -gon into several disjoint arcs which do not have a chord connecting their endpoints by definition. Suppose an arc had $w+2$ arcs, including endpoints. Using the same argument as the $n$ odd case, we can draw $((w+2)-3)+1 = w$ diagonals along this arc, where now include the longest edge is able to be counted as a diagonal.

Summing across all of these disjoint arcs, we get at most $n-w-2$ more diagonals on top of the $w$ in our web, giving our desired upper bound of $n-2$ . $\blacksquare$

This post has been edited 2 times. Last edited by shendrew7, Jan 15, 2025, 7:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

508 posts

Maximilian113

#37 h Jan 22, 2025, 4:41 PM

Y by

Note that whenever I say "interecting diagonals" I mean diagonals that intersect in the interior of the polygon.

For odd $n,$ there are clearly no pairs of perpendicular diagonals. Therefore, we can at best triangulate the polygon, giving us $n-3$ diagonals.

From here on, suppose that $n$ is even. We claim that the maximum is $n-2.$ If no two diagonals intersect, from the above logic we have at most $n-3$ diagonals. Therefore consider if there are two diagonals that intersect.

Now, we say that a pair of intersecting (and thus perpendicular) diagonals "span" $k$ consecutive vertices if $k$ is the minimum number of vertices required in a path from one vertice of the diagonals, traversing each consecutive vertice in some direction until we reach all $4$ endpoints of the diagonals at some point.

$\text{Lemma: }$ Each pair of perpendicular diagonals span at least $\frac{n}{2}+2$ vertices.

$\text{Proof: }$ Consider the arcs of the polygon's circumcircle formed from consecutive endpoints of our diagonals. Then the average of opposite arcs must be $90^\circ.$ Hence, each pair of arcs sum to $180^\circ.$ Since we want to minimize $k,$ we are looking to maximize the length of one arc, so we can take a path through the entire circle excluding this arc. Clearly, each arc subtends at least $1$ side, and opposite arcs subtend a total of $\frac{n}{2}$ sides meaning that the largest arc subtends $\frac{n}{2}-1$ sides. This gives $\frac{n}{2}-2$ vertices and therefore the spanning is always at least $n-\left( \frac{n}{2}-2 \right) = \frac{n}{2}+2.$

Therefore, if there is some pair of intersecting diagonals $\mathcal P$ every other pair of intersecting diagonals $\mathcal Q$ must have their diagonals intersect $\mathcal P.$ (As otherwise, we would require more vertices than the polygon has) Therefore, for each such set $\mathcal P$ and $\mathcal Q$ their diagonals' union must form a set $\mathcal S$ such that each pair of diagonals within it are either parallel or perpendicular to it.

From any valid configuration of diagonals, let $\mathcal S$ be largest set of such parallel and perpendicular diagonals, where to construct it we continuously add pairs of intersecting diagonals to it. Clearly from the above logic $\mathcal S$ is unique.

Now, for every diagonal in our configuration not in $\mathcal S,$ they must not intersect any other diagonal. The diagonals in $\mathcal S$ separate the polygon's vertices into disjoint maximized contiguous subblocks of vertices such that no vertices are an endpoint of some diagonal in $\mathcal S.$

In each such "group", the $x$ vertices, along with the $2$ vertices at both sides (these two vertices are both endpoints of some diagonal in $\mathcal S$ ), must connect in some way so that no two diagonals intersect. Obviously the optimal method would be to "triangulate" the polygon into as many vertices as possible. This creates at most $x-1$ diagonals.

Let there be $d$ diagonals in $\mathcal S.$ In addition, let $K$ be the set of vertices that are the endpoint of at least one diagonal in $\mathcal S.$ We claim that there are at least $2$ vertices in $K$ that are the endpoint of exactly one diagonal in $\mathcal S.$ For the sake of a contradiction, assume otherwise.

First of all, observe that each vertice in $K$ is the endpoint of at most two diagonals in $\mathcal S.$ Therefore each vertice of $K$ is the endpoint of two diagonals. In addition, by the definition of $\mathcal S,$ each of its diagonals is intersected by at least one other diagonal in $S.$

Thus consider a pair of diagonals. From each of these diagonals, we must introduce more diagonals in $\mathcal S$ to form "rectangles" in order for each vertice of $K$ to be the endpoints of two diagonals. But then we are always guaranteed to have pairs of opposite diagonals in each rectangle that don't intersect any diagonals in $\mathcal S,$ so there is some diagonal passing through a vertice within the subtended arcs. If we continue this process, we will eventually have more and more sides going "into" the arc, and eventually either we reach the midpoint of that arc, in which it is impossible to construct a new rectangle, or there is no midpoint of that arc. Both ways, there is a contradiction to one of the two properties we have stated. (this argument is pretty unclear, look at my diagram to maybe understand it better...)

Therefore, if there are $d$ diagonals in $\mathcal S,$ they eliminate at least $d+2$ vertices from the total number of vertices in the "groups". Each "group" adds at most the number of vertices it has to the total number of diagonals. There are $(n-d-2)$ total vertices among all the "groups", therefore we have at most $(n-d-2)+d=n$ diagonals, which proves the bound.

It suffices to find a construction, which is easy. Consider an arbitrary pair of intersecting diagonals. Then, triangulate each of the 4 "groups" around it. This yields $(n-4)+2=n-2$ diagonals, so the answer is indeed $n-2$ for $n$ even.

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

deduck

176 posts

deduck

#38 h Feb 20, 2025, 2:58 AM

Y by

SOMEONE CHECK IF THIS IS RIGHT PLS:

For odd case clearly there are no perpendicular diagonals so it's just triangulation, maximum is $n-2$ .

For even case: We will show the bound separately.

First define an A-type diagonal as follows: if some diagonal intersects another diagonal (at a right angle) inside the polygon, then it is A-type diagonal.

Now first draw all the A-type diagonals that we have. Note that this divides the polygon into several regions, and each of the regions that contains an edge adjacent to the outside of the polygon creates a "run" in the perimeter that is separated from the rest of the runs by A-type lines. I attached file with example, u can see it now.

Note that if there are $k$ A-type diagonals, that costs $2k$ vertices, so there are $n-2k$ vertices left that aren't an endpoint of an A-type diagonal. Note that if a run includes $x$ of these points, then there are $x+2$ vertices total in the run, which means there will be $x$ new diagonals maximum (since it must be a triangulation).

Now, since there are $n-2k$ vertices left that aren't an endpoint of an A-type diagonal, that means there are a maximum of $n-2k$ new diagonals. Adding to our beginning of $k$ A-type diagonals, then there are a total of $n-k$ diagonals.

Note that if there are $0$ A-type diagonals, then it must be $n-3$ , which is below our bound. There can't be only $1$ A-type diagonal, so there is at least $2$ A-type diagonals, then there are a maximum of $n-2$ diagonals. So the bound is proven

How to do the construction for even: Just keep pairing together adjacent sides to go from $n$ to $\frac{n}{2}$ sides, until we have some odd number of sides left. Then we can just draw $1$ A-type line from a vertex to the vertex opposite to it. So there are $n-2$ .

Attachments:

This post has been edited 1 time. Last edited by deduck, Feb 20, 2025, 2:59 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

endless_abyss

28 posts

endless_abyss

#39 h Mar 22, 2025, 10:46 AM

Y by

For odd - $n - 3$
Non-intersecting diagonals, achieved with triangulation.

For even - $n - 2$ , this follows from constructing mutual perpendiculars due to symmetry in even polygons, we construct $(2 a - 2)/2$ horizontally and $(2 a - 2)/2$ vertically. (Consider $n >= 8$ ) This bound follows from the fact that the diagonals must be perpendicular to a set of diagonals or parallel to another set, and we thus construct the maximum in the construction by using every two point to make a diagonal.

Z K Y

N Quick Reply