max no intersecting diag. in convex n-gon (2020-21 All-Siberian MO 8.4)

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

max no intersecting diag. in convex n-gon (2020-21 All-Siberian MO 8.4)

G H J

Reveal topic tags

combinatorial geometry

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

30629 posts

#1 h Feb 17, 2021, 12:03 PM • 1 Y

Y by son7

What is the largest number of non-intersecting diagonals that can be drawn in a convex $n$ -gon (diagonals with a common vertex are allowed)?

Z K Y

The post below has been deleted. Click to close.

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

Ninjasolver0201

722 posts

Ninjasolver0201

#2 h Feb 17, 2021, 3:35 PM • 3 Y

Y by Mango247, Mango247, Mango247

Claim: The answer is $\boxed{n-3}$ .

We can see that in a quadrilateral, we get $1$ diagonal. In a pentagon, $2$ diagonals and so on. Then we can prove the result with Induction.

Z K Y

The post below has been deleted. Click to close.

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

488 posts

#3 h Feb 17, 2021, 5:54 PM • 2 Y

Y by Mango247, Mango247

Let the points be $a_1, a_2, ..., a_n$ . The number of diagonals can be maximized when that all originate from the same point. Since a diagonal cannot be a side, we can say that the diagonals can be $a_1a_3, a_1a_4, ... a_1a_{n-2}, a_1a_{n-1}$ . This is $n-3$ diagonals.

Z K Y

The post below has been deleted. Click to close.

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

1703 posts

#4 h Feb 17, 2021, 6:16 PM

Y by

At a vertice of a quadrilateral, there are $n-2$ remaining sides, and there are $(n-2)-1 = n-3$ remaining vertices that don't coincide with a side of the $n-$ gon. Thus, the maximum is $n-3$ diagonals.

Z K Y

The post below has been deleted. Click to close.

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

sidchukkayapally

669 posts

sidchukkayapally

#5 h Feb 17, 2021, 6:40 PM

Y by

Claim: The answer is n - 3
Proof: Begin by examining a quadrilateral. Clearly, this only can have 1 diagonal drawn. Now showing that every time the number of sides of the convex polygon increases by 1, so does the number of diagonals.

Claim: Every time the number of sides of the convex polygon increases by 1, so does the number of diagonals.

Proof: Now let there be a convex polygon with n sides. Connect 2 vertices that have a vertex between them. This splits the figure into a triangle, and a convex n - 1 gon. Clearly the diagonal drawn, along with the possible number of diagonals in an n - 1 gon are possible, thus proving both claims.

This post has been edited 1 time. Last edited by sidchukkayapally, Feb 17, 2021, 6:40 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a