Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
Yesterday at 11:16 PM
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Yesterday at 11:16 PM
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
positive integers forming a perfect square
cielblue   0
6 minutes ago
Find all positive integers $n$ such that $2^n-n^2+1$ is a perfect square.
0 replies
cielblue
6 minutes ago
0 replies
Function equation
LeDuonggg   6
N 18 minutes ago by MathLuis
Find all functions $f: \mathbb{R^+} \rightarrow \mathbb{R^+}$ , such that for all $x,y>0$:
\[ f(x+f(y))=\dfrac{f(x)}{1+f(xy)}\]
6 replies
LeDuonggg
Yesterday at 2:59 PM
MathLuis
18 minutes ago
A nice and easy gem off of StackExchange
NamelyOrange   0
18 minutes ago
Source: https://math.stackexchange.com/questions/3818796/
Define $S$ as the set of all numbers of the form $2^i5^j$ for some nonnegative $i$ and $j$. Find (with proof) all pairs $(m,n)$ such that $m,n\in S$ and $m-n=1$.
0 replies
NamelyOrange
18 minutes ago
0 replies
at everystep a, b, c are replaced by a+\gcd(b,c), b+\gcd(a,c), c+\gcd(a,b)
NJAX   8
N an hour ago by Assassino9931
Source: 2nd Al-Khwarizmi International Junior Mathematical Olympiad 2024, Day2, Problem 8
Three positive integers are written on the board. In every minute, instead of the numbers $a, b, c$, Elbek writes $a+\gcd(b,c), b+\gcd(a,c), c+\gcd(a,b)$ . Prove that there will be two numbers on the board after some minutes, such that one is divisible by the other.
Note. $\gcd(x,y)$ - Greatest common divisor of numbers $x$ and $y$

Proposed by Sergey Berlov, Russia
8 replies
NJAX
May 31, 2024
Assassino9931
an hour ago
Increments and Decrements in Square Grid
ike.chen   23
N an hour ago by Andyexists
Source: ISL 2022/C3
In each square of a garden shaped like a $2022 \times 2022$ board, there is initially a tree of height $0$. A gardener and a lumberjack alternate turns playing the following game, with the gardener taking the first turn:
[list]
[*] The gardener chooses a square in the garden. Each tree on that square and all the surrounding squares (of which there are at most eight) then becomes one unit taller.
[*] The lumberjack then chooses four different squares on the board. Each tree of positive height on those squares then becomes one unit shorter.
[/list]
We say that a tree is majestic if its height is at least $10^6$. Determine the largest $K$ such that the gardener can ensure there are eventually $K$ majestic trees on the board, no matter how the lumberjack plays.
23 replies
ike.chen
Jul 9, 2023
Andyexists
an hour ago
4-var inequality
RainbowNeos   5
N 2 hours ago by RainbowNeos
Given $a,b,c,d>0$, show that
\[\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}\geq 4+\frac{8(a-c)^2}{(a+b+c+d)^2}.\]
5 replies
RainbowNeos
Yesterday at 9:31 AM
RainbowNeos
2 hours ago
Hard diophant equation
MuradSafarli   2
N 2 hours ago by MuradSafarli
Find all positive integers $x, y, z, t$ such that the equation

$$
2017^x + 6^y + 2^z = 2025^t
$$
is satisfied.
2 replies
MuradSafarli
2 hours ago
MuradSafarli
2 hours ago
An almost identity polynomial
nAalniaOMliO   6
N 2 hours ago by Primeniyazidayi
Source: Belarusian National Olympiad 2025
Let $n$ be a positive integer and $P(x)$ be a polynomial with integer coefficients such that $P(1)=1,P(2)=2,\ldots,P(n)=n$.
Prove that $P(0)$ is divisible by $2 \cdot 3 \cdot \ldots \cdot n$.
6 replies
nAalniaOMliO
Mar 28, 2025
Primeniyazidayi
2 hours ago
Euler's function
luutrongphuc   2
N 2 hours ago by KevinYang2.71
Find all real numbers \(\alpha\) such that for every positive real \(c\), there exists an integer \(n>1\) satisfying
\[
\frac{\varphi(n!)}{n^\alpha\,(n-1)!} \;>\; c.
\]
2 replies
luutrongphuc
5 hours ago
KevinYang2.71
2 hours ago
Wot n' Minimization
y-is-the-best-_   25
N 2 hours ago by john0512
Source: IMO SL 2019 A3
Let $n \geqslant 3$ be a positive integer and let $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a strictly increasing sequence of $n$ positive real numbers with sum equal to 2. Let $X$ be a subset of $\{1,2, \ldots, n\}$ such that the value of
\[
\left|1-\sum_{i \in X} a_{i}\right|
\]is minimised. Prove that there exists a strictly increasing sequence of $n$ positive real numbers $\left(b_{1}, b_{2}, \ldots, b_{n}\right)$ with sum equal to 2 such that
\[
\sum_{i \in X} b_{i}=1.
\]
25 replies
y-is-the-best-_
Sep 23, 2020
john0512
2 hours ago
Line AT passes through either S_1 or S_2
v_Enhance   88
N 2 hours ago by bjump
Source: USA December TST for 57th IMO 2016, Problem 2
Let $ABC$ be a scalene triangle with circumcircle $\Omega$, and suppose the incircle of $ABC$ touches $BC$ at $D$. The angle bisector of $\angle A$ meets $BC$ and $\Omega$ at $E$ and $F$. The circumcircle of $\triangle DEF$ intersects the $A$-excircle at $S_1$, $S_2$, and $\Omega$ at $T \neq F$. Prove that line $AT$ passes through either $S_1$ or $S_2$.

Proposed by Evan Chen
88 replies
v_Enhance
Dec 21, 2015
bjump
2 hours ago
Inequality with a,b,c
GeoMorocco   4
N 3 hours ago by Natrium
Source: Morocco Training
Let $   a,b,c   $ be positive real numbers such that : $   ab+bc+ca=3   $ . Prove that : $$\frac{\sqrt{1+a^2}}{1+ab}+\frac{\sqrt{1+b^2}}{1+bc}+\frac{\sqrt{1+c^2}}{1+ca}\ge \sqrt{\frac{3(a+b+c)}{2}}$$
4 replies
GeoMorocco
Apr 11, 2025
Natrium
3 hours ago
China Northern MO 2009 p4 CNMO
parkjungmin   1
N 3 hours ago by WallyWalrus
Source: China Northern MO 2009 p4 CNMO P4
The problem is too difficult.
1 reply
parkjungmin
Apr 30, 2025
WallyWalrus
3 hours ago
Polynomial Squares
zacchro   26
N 3 hours ago by Mathandski
Source: USA December TST for IMO 2017, Problem 3, by Alison Miller
Let $P, Q \in \mathbb{R}[x]$ be relatively prime nonconstant polynomials. Show that there can be at most three real numbers $\lambda$ such that $P + \lambda Q$ is the square of a polynomial.

Alison Miller
26 replies
zacchro
Dec 11, 2016
Mathandski
3 hours ago
2011-gon
3333   27
N Apr 10, 2025 by Maximilian113
Source: All-Russian 2011
A convex 2011-gon is drawn on the board. Peter keeps drawing its diagonals in such a way, that each newly drawn diagonal intersected no more than one of the already drawn diagonals. What is the greatest number of diagonals that Peter can draw?
27 replies
3333
May 17, 2011
Maximilian113
Apr 10, 2025
2011-gon
G H J
Source: All-Russian 2011
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
3333
667 posts
#1 • 2 Y
Y by Adventure10, Mango247
A convex 2011-gon is drawn on the board. Peter keeps drawing its diagonals in such a way, that each newly drawn diagonal intersected no more than one of the already drawn diagonals. What is the greatest number of diagonals that Peter can draw?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mavropnevma
15142 posts
#2 • 2 Y
Y by Adventure10, Mango247
Are two diagonals sharing a common vertex considered to intersect ?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
301EC
48 posts
#3 • 1 Y
Y by Adventure10
I don't think so!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JBL
16123 posts
#4 • 2 Y
Y by Adventure10, Mango247
For $n \geq 3$, let $f(n)$ be the maximal number for an $n$-gon, and for convenience set $f(2) = -1$. Suppose the $n$-gon has vertices $A_1$, $A_2$, ..., $A_n$. Certainly, any optimal configuration contains at least one pair of crossing diagonals, say $A_1 A_j$ and $A_i A_k$. To any such configuration we can add the diagonals $A_1 A_i$, $A_i A_j$, $A_j A_k$ and $A_k A_1$ if they do not already appear without creating any new crossings. Moreover, doing so makes clear that the problem decomposes into four smaller versions of the same problem, with $i$, $j - i + 1$, $k - j + 1$ and $n + 2 - k$ vertices. It follows immediately that
\[
f(n) = 6 + \max_{\substack{i, j, k \\ 1 < i < j < k \leq n}}( f(i) + f(j - i + 1) + f(k - j + 1) + f(n + 2 - k)).
\]
Now prove by induction that $f(n) = n + \lfloor n/2 \rfloor - 4$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mymath7
162 posts
#5 • 5 Y
Y by JBL, Adventure10, Mango247, DEKT, and 1 other user
JBL wrote:
Now prove by induction that $f(n) = n + \lfloor n/2 \rfloor - 4$.

Nice try, but this is clearly wrong. Take $n=5$ for example. If the pentagon is $ABCDE$, we can draw $AD, BE, CE, CA$ in that order. This yields $4$ diagonals. In your formula, $f(5) = 5 + \lfloor 5/2 \rfloor -4 = 3$. :)

Hint: $f(3) = 0, f(4) = 2, f(5) = 4, \ldots$ :)
mavropnevma wrote:
Are two diagonals sharing a common vertex considered to intersect ?

Pedantic as always. No :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JBL
16123 posts
#6 • 2 Y
Y by Adventure10, Mango247
Ah, you're right, I didn't read carefully: my solution asks that no diagonal crosses more than one other, regardless of the times they were drawn.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mavropnevma
15142 posts
#7 • 1 Y
Y by Adventure10
mymath7 wrote:
mavropnevma wrote:
Are two diagonals sharing a common vertex considered to intersect ?

Pedantic as always. No :)
Not that pedantic ... In the thrackle definition (see Conway's thrackle conjecture), two edges of a thrackle are considered to meet if they have a common endpoint, not just if their crossing is transverse.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mymath7
162 posts
#8 • 6 Y
Y by Adventure10 and 5 other users
mavropnevma wrote:
Not that pedantic ... In the thrackle definition (see Conway's thrackle conjecture), two edges of a thrackle are considered to meet if they have a common endpoint, not just if their crossing is transverse.

I was by no means saying that your pedantry is a bad thing. Indeed, with one problem that is clearly stated to others, you are able to generate dozens of other interpretations for people to solve :)
JBL wrote:
Ah, you're right, I didn't read carefully: my solution asks that no diagonal crosses more than one other, regardless of the times they were drawn.

Yes, but we can still use apply your idea with the correct version. Supposing that $A_1A_j$ is the last diagonal drawn, and $A_iA_k$ is the only one crossing it, we can induct on the two polygons $A_1A_2...A_j$ and $A_j...A_1$, after which we are essentially done. :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mewto55555
4210 posts
#9 • 3 Y
Y by NewAlbionAcademy, Adventure10, Mango247
Rough sketch since there's no solution yet:

First we prove inductively that we can get $2(n-3)$. Base cases are obvious. Now, assume we have $2(n-3)$ diagonals drawn on points $A_1,A_2,...,A_n$. WLOG add point $A_{n+1}$ after $A_n$ and before $A_1$. Then we can draw diagonals $A_nA_1$ and then $A_{n+1}A_2$ in that order.

(this part was not my idea): To prove $2(n-3)$ is the maximum, draw two n-gons side by side, each with diagonals that never cross. At best, we can get $(n-3)$ in each, super-imposing them gives $2(n-3)$ is the best -- if any side has more, then we would have to draw a diagonal with two intersections.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MBGO
315 posts
#10 • 3 Y
Y by Adventure10, Mango247, jkim0656
proof of maximality is quite incorrect.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
sahadian
112 posts
#11 • 2 Y
Y by Adventure10, Mango247
I think something wrong in your answer if the answer is $2(n-3)$ it means that for $n=3$ we cant draw any diagonal but it is Obvious that we can draw at least 1 diagonal for n=3
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
brothers-brt
32 posts
#12 • 2 Y
Y by Adventure10, Mango247
you've made a mistake. A BIG ONE ;D
when you draw a(n+1),a(2) diagonal it intersects all diagonals that exit from a(1) and they might be more than one
so the induction is wrong tooooooo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
numbertheorist17
268 posts
#13 • 1 Y
Y by Adventure10
So is there actually a correct solution?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
junioragd
314 posts
#14 • 2 Y
Y by Adventure10, Mango247
The answer is 2*(n-3).Let the number of diagonals be c.Now,there are at most c-1 intersections.Also,if we pick a random subset of diagonals,such that subset has k diagonals,there are also a t most k-1 intersections(we consider the intersections only among the diagonals in the subset,the inersection of a diagonal which is not in the subset with a diagonal which is in the subset doesn't count),or in another words,subset must consider the conditions of the whole set.Now,WLOG suppose that the last drawn diagonal is A1Ai(we can clockwise move indexes),because the indexing will be easyer.Now,we use induction on polygons A1A2...Ai and AiAi+1...AnA1,and also we can add one more diagonal that isn't in any of the polygons,than it intersects A1Ai.Now,by pure induction we have that the maximum number of diagonals is 2*(i-3)+2*(n-i-1)+2=2*n-6=2*(n-3)(The induction base for n=3 and n=4 is obvious).Now,the example for 2*(n-3):Draw diagonals in this order:
A1A3,A2A4,A3A5...An-1A1,A1A4,A1A5,A1A6,...A1An-2 and we are finished
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SmartClown
82 posts
#15 • 1 Y
Y by Adventure10
First solution:answer is $2(n-3)$. $n=3$ and $n=4$ cases are trivial.Now consider and $n-gon$.By considering the last drawn diagonal and by induction hypotesis(strong induction) applied on $2$ polygon the last diagonal divides the $n-gon$ and of course adding $2$ for the last diagonal and the diagonal that is intersected by it we easily obtain: $2(n-3)$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SmartClown
82 posts
#16 • 2 Y
Y by magicarrow, Adventure10
Now the second solution: We will prove that we can divide the diagonals in $2$ subsets such that no $2$ diagonals from the same subset intersect each other.It is done by greedy algorithm.Let the first diagonal drawn be colored blue.Now for every next diagonal drawn if it intersects a blue diagonal we color it red.Otherwise we color it blue.Now we easily see that no $2$ blue diagonals or $2$ red diagonals intersect each other so we proved that our subsets exist.Now number of diagonals in both subsets is $\le n-3$ so the maximum number is $\le 2(n-3)$.Then we just give an example which is not hard.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
va2010
1276 posts
#17 • 3 Y
Y by Wizard_32, Adventure10, Mango247
The answer is $2(n-3)$. Let the polygon be $A_1A_2 \cdots A_n$. Now, go with $A_{k-1}A_{k+1}$ and then $A_1A_k$ for $k = 3$ through $k = n-1$. The only diagonals that $A_{k-1}A_{k+1}$ can cross are $A_{k-2}A_{k}$ and $A_1 A_k$, the second of which comes after. On the other hand, the only diagonal that $A_1A_k$ can ever cross is $A_{k-1}A_{k+1}$. Hence, this construction works.

We prove that $2(n-3)$ is the largest possible value. Let the answer for an $n$-gon be $f(n)$, and observe that $f(3) = 0$, $f(4) = 2$. We use induction. Now look at the last drawn diagonal, and let it divide the polygon into an $a$-gon and a $b$-gon, where $a + b = n+2$. Now see that there can be at most one diagonal that crosses the diagonal, and that the maximal number of diagonals completely within the $a$-gon and the $b$-gon sum to $f(a)+f(b)$. Hence, it is clear that \[ f(n) \le f(a) + f(b) + 2 = 2(a+b-6) + 2 = 2(n-4) + 2 = 2(n-3) \], so our induction is complete and the answer is $2(n-3)$, as desired.
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
#19 • 1 Y
Y by jkim0656
The answer is $2n-6$ diagonals for general $n$. Let the polygon be $A_1A_2A_3\cdots A_n$.

For a construction, construct $n-1$ diagonals $\overline{A_iA_{i+2}}$ for $1 \leq i \leq n-1$, where indices are cyclic. Then, construct $n-5$ diagonals $\overline{A_1A_j}$ for $4 \leq j \leq n-2$, in that order.

To prove the bound, we argue inductively. Let $\ell$ be the last diagonal that was drawn. Then, $\ell$ intersects at most one other diagonal. All other diagonals must be contained in a $a+1$-gon or $b+1$-gon that $\ell$ partitions the $n$-gon into, where $a+b = n$. Thus, by the inductive hypothesis, the number of diagonals $$f(n) \leq f(a+1) + f(b+1) + 2 \leq (n-4)+(n-4) + 2 = 2n-6,$$as needed.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EhsanHeidari
6 posts
#20 • 1 Y
Y by Parham.moshashaee
intresting fact:
This graph is planner graph and thats prove
how number of diagonals is at most $3n-6-n=2n-6$.
for proving this claim we just draw diagonals until we cant ،then we draw that edge from outside of polygon.if somewhere we cant do this ,thats result in a diagonal must intersect at least two others.that is contradiction.
so this graph is planner.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
joshualiu315
2533 posts
#21
Y by
We will show that the general result for an $n$-gon is $2n-6$. As a construction, in polygon $A_1A_2\dots A_n$, draw $A_iA_{i+2}$ for $1 \le i \le n-1$ and $A_1A_j$ for $4 \le j \le n-2$, where indices are modulo $n$.

To show that this is optimal, we will use strong induction. Suppose the inductive hypothesis holds for all $n < k$. Let the final diagonal drawn in a $k$-gon be $\ell$. Note that $\ell$ intersects at most $1$ other diagonal by the problem condition. Furthermore, suppose that $\ell$ splits the $k$-gon into an $(a+1)$-gon and a $(b+1)$-gon such that $a+b=k$ and $a,b<k$. The total number of diagonals is hence

\[(2(a+1)-6)+(2(b+1)-6)+2=2a+2b-6=2k-6,\]
completing the induction.

At this point, simply plugging $2011$ into the general formula yields $\boxed{4016}$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
kamatadu
480 posts
#22 • 1 Y
Y by GeoKing
Let $n=2011$. The answer is $2n-6$ diagonals. We proceed by using strong induction. The base cases $n=3$ and $n=4$ can be checked by hand.

Now $\ell_1$ be the diagonal that we draw last. There is at most one more diagonal that intersects $\ell_1$.

So if $\ell_1$ divides the $n$ points into $p$ and $q$ points (the two partitions are disjoint, except that they both share the common points of $\ell_1$), then we get that the maximum number of diagonals is,
\[ \le (2p-6) + (2q-6) + 2= 2p + 2q -10 = 2(p+q-2) -6. \]
The $2$ in the first step are due to counting the two diagonals $\ell_1$ and $\ell_2$.

This completes our induction and we are done. The construction can also be done inductively. :yoda:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dolphinday
1324 posts
#23
Y by
This is kind of dumb.
The greatest number of diagonals for an $n$-gon is $2n - 6$. We will prove this using induction.
$\newline$
Base Case:
$\newline$
We can see that for a triangle with $3$-side, this is obviously true.
$\newline$
Inductive Step:
$\newline$
The last diagonal we draw splits our polygon into an $p + 1$ sided polygon and a $q + 1$ sided polygon. Note that $p + q = n$.
$\newline$
Due the intersecting diagonal, the last diagonal can only intersect with another diagonal once.$\newline$
Then the total number of diagonals in our polygon(while assuming our formula to be true for the $p + 1$-sided polygon and the $q + 1$-sided polygon) is
$2(p + 1) - 6 + 2(q + 1) - 6 + 2$.(we add two, because we count the last diagonal and the diagonal that intersects the last diagonal)
$2(p + 1) - 6 + 2(q + 1) - 6 + 2 = 2(p + q) - 6 = 2n - 6$ so we are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cursed_tangent1434
611 posts
#24
Y by
We solve the more general problem for a $n-$gon. Let $d(n)$ denote the maximum number of diagonals Peter can draw for a $n-$gon. We proceed via induction.

First note that $d(4)=2$ since that is the maximum number of total diagonals we can draw in a quadrilateral (and you can draw both without any issue). Now, consider a $n-$ gon for $n\geq 5$. Assume that for all $1 \leq k <n$ we have that $d(k) = 2(k-3)$. Then, we simply consider the last diagonal drawn in the $n-$gon. This separates the $n-$gon into two polygons with $a+2$ and $b+2$ vertices each such that $n=a+b+2$. Then,
\[d(n)  = 2 + d(a+2)+d(b+2)= 2+ 2(a-1)+2(b-1)=2(a+b-1) = 2((a+b+2)-3)=2(n-3)\](Here the leading +2 is due to the last drawn diagonal and the one and only diagonal with intersects it (if there are two or more we are not able to draw the last diagonal)). Thus, the induction is complete.

Now, this means the maximum number of diagonals Peter can drawn in a $2011-$gon is
\[d(2011)=2(2011-3)=2(2008)=4016\]diagonals.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
794 posts
#25
Y by
We claim that our answer is $\boxed{2n-6}$ for any $n$-gon. We can prove this bound and constructability through strong induction.

We show that a $k$-gon satisfies the inductive hypothesis given that 3-, 4-, $\ldots$, $(k-1)$-gons all hold. Note that the last diagonal drawn divides the $k$-gon into an $m$-gon and a $k+2-m$-gon. Also, this final diagonal must only intersect with at most one other diagonal, so our maximum bound is
\[(2m-6) + (2(k+2-m)-6) + 2 = 2k - 6,\]
as desired. This is achievable by simply taking 4 consecutive vertices $ABCD$ (in order) and setting $AC$ as the final diagonal and $BD$ as the only diagonal crossing $AC$. We are left with a $(k-1)$-gon that we can start constructing by drawing edges from $C$, so we indeed have $2(k-1)-6+2=2k-6$ diagonals. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bebebe
992 posts
#26
Y by
We claim that for a $n$-gon the greatest number of diagonals that can be drawn is $2n-6$. Base cases $n=3, 4$ work.


We use strong induction. Consider the last diagonal we draw. Say it splits the $n$-gon into a $p+1$-gon and a $q+1$-gon where $p+q=n.$ We also know that since most one diagonal intersects the last diagonal, at most one diagonal goes between the $p+1$ and $q+1$ gons. Thus, the maximal diagonals is $$2(p+1)-6 + 2(q+1)-6 + 2 = 2n - 6.$$

We need to show that this is achievable. For this we just need regular induction. Assume $2(n-1)-6$ diagonals is achievable for $n-1$-gon. There exists a vertex, $V$, on the $n-1$-gon such that the number of diagonals going through it is at most $1$ (can be easily shown by contradiction). Let the neighbors of $V$ be $N_1, N_2.$ Now to construct our $n$-gon, insert a new vertex, $N$ beween $V$ and $N_1.$ Finally draw the edges $NN_2$ then $VN_1.$ This $n$-gon will have $2(n-1)-6+2=2n-6$ edges, ad desired. \qed
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Marcus_Zhang
980 posts
#27
Y by
Sol with bad write up

Interesting. The answer is $2n - 6$but if you consider $0$ intersections, the answer appears to be $n - 3$...
This post has been edited 3 times. Last edited by Marcus_Zhang, Apr 10, 2025, 3:20 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eg4334
637 posts
#29
Y by
Boring problem. The answer is $2n-6$. In a cylic fashion starting with $A_1$, draw $A_iA_{i+2}$ for $i = 1, 2, \dots n-1$ in that order. Now from $A_1A_i$ for $i=4, 5, \dots n-2$ in that order. This gives $n-1+n-5 = 2n-6$.

Now we prove the result by strong induction. Consider the last diagonal drawn, which can intersect another one. It splits the $n$ gon into an $m$ gon and $n+2-m$ gon obviously. Then, we have a maximum of $2m-6 + 2(n+2-m)-6 + 2 = 2n -6$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
574 posts
#30
Y by
Did this before, going to post it now ig

We claim that the answer is $2n-6.$ We proceed with induction on $n.$ The base cases, $n=3, 4$ are trivial. Now suppose that the proposition holds for all $n \leq k$ for some positive integer $k \geq 4.$ Then consider a $k+1$-gon. Note that the last diagonal drawn intersects with at most one other diagonal. If this last diagonal separates the polygon into an $m$-gon and a $k-m+3$-gon, then by the inductive hypothesis we have at most $$2m-6+2(k-m+3)-6+2 = 2k-4 = 2(k+1)-6.$$Thus the bound is proven. For the construction, just consider construct $n-1$ diagonals of the form $P_i P_{i+2}$ for $1 \leq i \leq n-1,$ and then $n-5$ diagonals of the form $A_1A_j$ for $4 \leq j \leq n-2.$ Thus the induction is complete, so $2n-6$ is indeed the answer.
Z K Y
N Quick Reply
G
H
=
a