Summer is a great time to explore cool problems to keep your skills sharp!  Schedule a class today!

G
Topic
First Poster
Last Poster
k a June Highlights and 2025 AoPS Online Class Information
jlacosta   0
4 hours ago
Congratulations to all the mathletes who competed at National MATHCOUNTS! If you missed the exciting Countdown Round, you can watch the video at this link. Are you interested in training for MATHCOUNTS or AMC 10 contests? How would you like to train for these math competitions in half the time? We have accelerated sections which meet twice per week instead of once starting on July 8th (7:30pm ET). These sections fill quickly so enroll today!

[list][*]MATHCOUNTS/AMC 8 Basics
[*]MATHCOUNTS/AMC 8 Advanced
[*]AMC 10 Problem Series[/list]
For those interested in Olympiad level training in math, computer science, physics, and chemistry, be sure to enroll in our WOOT courses before August 19th to take advantage of early bird pricing!

Summer camps are starting this 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 a transformative 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][*]June 5th, Thursday, 7:30pm ET: Open Discussion with Ben Kornell and Andrew Sutherland, Art of Problem Solving's incoming CEO Ben Kornell and CPO Andrew Sutherland host an Ask Me Anything-style chat. Come ask your questions and get to know our incoming CEO & CPO!
[*]June 9th, Monday, 7:30pm ET, Game Jam: Operation Shuffle!, Come join us to play our second round of Operation Shuffle! If you enjoy number sense, logic, and a healthy dose of luck, this is the game for you. No specific math background is required; all are welcome.[/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
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29
Sunday, Aug 17 - Dec 14
Tuesday, Aug 26 - Dec 16
Friday, Sep 5 - Jan 16
Monday, Sep 8 - Jan 12
Tuesday, Sep 16 - Jan 20 (4:30 - 5:45 pm ET/1:30 - 2:45 pm PT)
Sunday, Sep 21 - Jan 25
Thursday, Sep 25 - Jan 29
Wednesday, Oct 22 - Feb 25
Tuesday, Nov 4 - Mar 10
Friday, Dec 12 - Apr 10

Prealgebra 2 Self-Paced

Prealgebra 2
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21
Sunday, Aug 17 - Dec 14
Tuesday, Sep 9 - Jan 13
Thursday, Sep 25 - Jan 29
Sunday, Oct 19 - Feb 22
Monday, Oct 27 - Mar 2
Wednesday, Nov 12 - Mar 18

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28
Sunday, Aug 17 - Dec 14
Wednesday, Aug 27 - Dec 17
Friday, Sep 5 - Jan 16
Thursday, Sep 11 - Jan 15
Sunday, Sep 28 - Feb 1
Monday, Oct 6 - Feb 9
Tuesday, Oct 21 - Feb 24
Sunday, Nov 9 - Mar 15
Friday, Dec 5 - Apr 3

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 2 - Sep 17
Sunday, Jul 27 - Oct 19
Monday, Aug 11 - Nov 3
Wednesday, Sep 3 - Nov 19
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Friday, Oct 3 - Jan 16
Tuesday, Nov 4 - Feb 10
Sunday, Dec 7 - Mar 8

Introduction to Number Theory
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30
Wednesday, Aug 13 - Oct 29
Friday, Sep 12 - Dec 12
Sunday, Oct 26 - Feb 1
Monday, Dec 1 - Mar 2

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14
Thursday, Aug 7 - Nov 20
Monday, Aug 18 - Dec 15
Sunday, Sep 7 - Jan 11
Thursday, Sep 11 - Jan 15
Wednesday, Sep 24 - Jan 28
Sunday, Oct 26 - Mar 1
Tuesday, Nov 4 - Mar 10
Monday, Dec 1 - Mar 30

Introduction to Geometry
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19
Wednesday, Aug 13 - Feb 11
Tuesday, Aug 26 - Feb 24
Sunday, Sep 7 - Mar 8
Thursday, Sep 11 - Mar 12
Wednesday, Sep 24 - Mar 25
Sunday, Oct 26 - Apr 26
Monday, Nov 3 - May 4
Friday, Dec 5 - May 29

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
Friday, Aug 8 - Feb 20
Tuesday, Aug 26 - Feb 24
Sunday, Sep 28 - Mar 29
Wednesday, Oct 8 - Mar 8
Sunday, Nov 16 - May 17
Thursday, Dec 11 - Jun 4

Intermediate Counting & Probability
Sunday, Jun 22 - Nov 2
Sunday, Sep 28 - Feb 15
Tuesday, Nov 4 - Mar 24

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

Precalculus
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8
Wednesday, Aug 6 - Jan 21
Tuesday, Sep 9 - Feb 24
Sunday, Sep 21 - Mar 8
Monday, Oct 20 - Apr 6
Sunday, Dec 14 - May 31

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Wednesday, Jun 25 - Dec 17
Sunday, Sep 7 - Mar 15
Wednesday, Sep 24 - Apr 1
Friday, Nov 14 - May 22

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
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!)
Sunday, Aug 17 - Nov 9
Wednesday, Sep 3 - Nov 19
Tuesday, Sep 16 - Dec 9
Sunday, Sep 21 - Dec 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Oct 6 - Jan 12
Thursday, Oct 16 - Jan 22
Tues, Thurs & Sun, Dec 9 - Jan 18 (meets three times a week!)

MATHCOUNTS/AMC 8 Advanced
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)
Sunday, Aug 17 - Nov 9
Tuesday, Aug 26 - Nov 11
Thursday, Sep 4 - Nov 20
Friday, Sep 12 - Dec 12
Monday, Sep 15 - Dec 8
Sunday, Oct 5 - Jan 11
Tues, Thurs & Sun, Dec 2 - Jan 11 (meets three times a week!)
Mon, Wed & Fri, Dec 8 - Jan 16 (meets three times a week!)

AMC 10 Problem Series
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!)
Sunday, Aug 10 - Nov 2
Thursday, Aug 14 - Oct 30
Tuesday, Aug 19 - Nov 4
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Mon, Wed & Fri, Oct 6 - Nov 3 (meets three times a week!)
Tue, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 10 Final Fives
Monday, Jun 30 - Jul 21
Friday, Aug 15 - Sep 12
Sunday, Sep 7 - Sep 28
Tuesday, Sep 9 - Sep 30
Monday, Sep 22 - Oct 13
Sunday, Sep 28 - Oct 19 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, Oct 8 - Oct 29
Thursday, Oct 9 - Oct 30

AMC 12 Problem Series
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22
Sunday, Aug 10 - Nov 2
Monday, Aug 18 - Nov 10
Mon & Wed, Sep 15 - Oct 22 (meets twice a week!)
Tues, Thurs & Sun, Oct 7 - Nov 2 (meets three times a week!)

AMC 12 Final Fives
Thursday, Sep 4 - Sep 25
Sunday, Sep 28 - Oct 19
Tuesday, Oct 7 - Oct 28

AIME Problem Series A
Thursday, Oct 23 - Jan 29

AIME Problem Series B
Sunday, Jun 22 - Sep 21
Tuesday, Sep 2 - Nov 18

F=ma Problem Series
Wednesday, Jun 11 - Aug 27
Tuesday, Sep 16 - Dec 9
Friday, Oct 17 - Jan 30

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
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
Thursday, Aug 14 - Oct 30
Sunday, Sep 7 - Nov 23
Tuesday, Dec 2 - Mar 3

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22
Friday, Oct 3 - Jan 16

USACO Bronze Problem Series
Sunday, Jun 22 - Sep 1
Wednesday, Sep 3 - Dec 3
Thursday, Oct 30 - Feb 5
Tuesday, Dec 2 - Mar 3

Physics

Introduction to Physics
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15
Tuesday, Sep 2 - Nov 18
Sunday, Oct 5 - Jan 11
Wednesday, Dec 10 - Mar 11

Physics 1: Mechanics
Monday, Jun 23 - Dec 15
Sunday, Sep 21 - Mar 22
Sunday, Oct 26 - Apr 26

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
4 hours ago
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
IMO ShortList 2008, Number Theory problem 2
April   40
N 7 minutes ago by ezpotd
Source: IMO ShortList 2008, Number Theory problem 2, German TST 2, P2, 2009
Let $ a_1$, $ a_2$, $ \ldots$, $ a_n$ be distinct positive integers, $ n\ge 3$. Prove that there exist distinct indices $ i$ and $ j$ such that $ a_i + a_j$ does not divide any of the numbers $ 3a_1$, $ 3a_2$, $ \ldots$, $ 3a_n$.

Proposed by Mohsen Jamaali, Iran
40 replies
April
Jul 9, 2009
ezpotd
7 minutes ago
IMO Genre Predictions
ohiorizzler1434   75
N 10 minutes ago by Mysteriouxxx
Everybody, with IMO upcoming, what are you predictions for the problem genres?


Personally I predict: predict
75 replies
ohiorizzler1434
May 3, 2025
Mysteriouxxx
10 minutes ago
A weird problem
jayme   2
N 29 minutes ago by lolsamo
Dear Mathlinkers,

1. ABC a triangle
2. 0 the circumcircle
3. I the incenter
4. 1 a circle passing througn B and C
5. X, Y the second points of intersection of 1 wrt BI, CI
6. 2 the circumcircle of the triangle XYI
7. M, N the symetrics of B, C wrt XY.

Question : if 2 is tangent to 0 then, 2 is tangent to MN.

Sincerely
Jean-Louis
2 replies
jayme
Today at 6:52 AM
lolsamo
29 minutes ago
Channel name changed
Plane_geometry_youtuber   10
N 31 minutes ago by Yiyj
Hi,

Due to the search handle issue in youtube. My channel is renamed to Olympiad Geometry Club. And the new link is as following:

https://www.youtube.com/@OlympiadGeometryClub

Recently I introduced the concept of harmonic bundle. I will move on to the conjugate median soon. In the future, I will discuss more than a thousand theorems on plane geometry and hopefully it can help to the students preparing for the Olympiad competition.

Please share this to the people may need it.

Thank you!
10 replies
Plane_geometry_youtuber
Yesterday at 9:31 PM
Yiyj
31 minutes ago
1 x 3 pieces in a 3 x 25 board,m max no of pieces placed
parmenides51   1
N an hour ago by TheBaiano
Source: Lusophon 2018 CPLP P6
In a $3 \times 25$ board, $1 \times 3$ pieces are placed (vertically or horizontally) so that they occupy entirely $3$ boxes on the board and do not have a common point.
What is the maximum number of pieces that can be placed, and for that number, how many configurations are there?

original formulation
1 reply
parmenides51
Sep 13, 2018
TheBaiano
an hour ago
smallest a so that S(n)-S(n+a) = 2018, where S(n)=sum of digits
parmenides51   3
N an hour ago by TheBaiano
Source: Lusophon 2018 CPLP P3
For each positive integer $n$, let $S(n)$ be the sum of the digits of $n$. Determines the smallest positive integer $a$ such that there are infinite positive integers $n$ for which you have $S (n) -S (n + a) = 2018$.
3 replies
parmenides51
Sep 13, 2018
TheBaiano
an hour ago
Ducks can play games now apparently
MortemEtInteritum   35
N 2 hours ago by pi271828
Source: USA TST(ST) 2020 #1
Let $a$, $b$, $c$ be fixed positive integers. There are $a+b+c$ ducks sitting in a
circle, one behind the other. Each duck picks either rock, paper, or scissors, with $a$ ducks
picking rock, $b$ ducks picking paper, and $c$ ducks picking scissors.
A move consists of an operation of one of the following three forms:

[list]
[*] If a duck picking rock sits behind a duck picking scissors, they switch places.
[*] If a duck picking paper sits behind a duck picking rock, they switch places.
[*] If a duck picking scissors sits behind a duck picking paper, they switch places.
[/list]
Determine, in terms of $a$, $b$, and $c$, the maximum number of moves which could take
place, over all possible initial configurations.
35 replies
MortemEtInteritum
Nov 16, 2020
pi271828
2 hours ago
2017 IGO Advanced P3
bgn   18
N 2 hours ago by Circumcircle
Source: 4th Iranian Geometry Olympiad (Advanced) P3
Let $O$ be the circumcenter of triangle $ABC$. Line $CO$ intersects the altitude from $A$ at point $K$. Let $P,M$ be the midpoints of $AK$, $AC$ respectively. If $PO$ intersects $BC$ at $Y$, and the circumcircle of triangle $BCM$ meets $AB$ at $X$, prove that $BXOY$ is cyclic.

Proposed by Ali Daeinabi - Hamid Pardazi
18 replies
bgn
Sep 15, 2017
Circumcircle
2 hours ago
Own made functional equation
JARP091   1
N 3 hours ago by JARP091
Source: Own (Maybe?)
\[
\text{Find all functions } f : \mathbb{R} \to \mathbb{R} \text{ such that:} \\
f(a^4 + a^2b^2 + b^4) = f\left((a^2 - f(ab) + b^2)(a^2 + f(ab) + b^2)\right)
\]
1 reply
JARP091
May 31, 2025
JARP091
3 hours ago
Euler line of incircle touching points /Reposted/
Eagle116   6
N 3 hours ago by pigeon123
Let $ABC$ be a triangle with incentre $I$ and circumcentre $O$. Let $D,E,F$ be the touchpoints of the incircle with $BC$, $CA$, $AB$ respectively. Prove that $OI$ is the Euler line of $\vartriangle DEF$.
6 replies
Eagle116
Apr 19, 2025
pigeon123
3 hours ago
Parallel lines on a rhombus
buratinogigle   1
N 4 hours ago by Giabach298
Source: Own, Entrance Exam for Grade 10 Admission, HSGS 2025
Given the rhombus $ABCD$ with its incircle $\omega$. Let $E$ and $F$ be the points of tangency of $\omega$ with $AB$ and $AC$ respectively. On the edges $CB$ and $CD$, take points $G$ and $H$ such that $GH$ is tangent to $\omega$ at $P$. Suppose $Q$ is the intersection point of the lines $EG$ and $FH$. Prove that two lines $AP$ and $CQ$ are parallel or coincide.
1 reply
buratinogigle
5 hours ago
Giabach298
4 hours ago
Orthocenter lies on circumcircle
whatshisbucket   90
N 4 hours ago by bjump
Source: 2017 ELMO #2
Let $ABC$ be a triangle with orthocenter $H,$ and let $M$ be the midpoint of $\overline{BC}.$ Suppose that $P$ and $Q$ are distinct points on the circle with diameter $\overline{AH},$ different from $A,$ such that $M$ lies on line $PQ.$ Prove that the orthocenter of $\triangle APQ$ lies on the circumcircle of $\triangle ABC.$

Proposed by Michael Ren
90 replies
whatshisbucket
Jun 26, 2017
bjump
4 hours ago
Polish MO Finals 2014, Problem 4
j___d   3
N 4 hours ago by ariopro1387
Source: Polish MO Finals 2014
Denote the set of positive rational numbers by $\mathbb{Q}_{+}$. Find all functions $f: \mathbb{Q}_{+}\rightarrow \mathbb{Q}_{+}$ that satisfy
$$\underbrace{f(f(f(\dots f(f}_{n}(q))\dots )))=f(nq)$$for all integers $n\ge 1$ and rational numbers $q>0$.
3 replies
j___d
Jul 27, 2016
ariopro1387
4 hours ago
S(an) greater than S(n)
ilovemath0402   1
N 4 hours ago by ilovemath0402
Source: Inspired by an old result
Find all positive integer $n$ such that $S(an)\ge S(n) \quad \forall a \in \mathbb{Z}^{+}$ ($S(n)$ is sum of digit of $n$ in base 10)
P/s: Original problem
1 reply
ilovemath0402
5 hours ago
ilovemath0402
4 hours ago
Olympiad Combinatorics Book
Pascal96   126
N Dec 27, 2023 by zaahir
Hi everyone, I am currently writing a book on combinatorics for people preparing for national and international math competitions, especially the IMO and selection tests leading up to it. The book is intended to expose readers to a variety of ideas, techniques and problem solving strategies, ranging from the intuitive “greedy algorithms” in the first chapter to the powerful Probabilistic Method in chapter nine.
I am uploading chapter one here, and would appreciate your feedback and any suggestions. Over the coming weeks, I will be uploading the remaining chapters one at a time.
The only prerequisites are familiarity with basic graph theoretic concepts and terminology, algebraic inequalities, induction and the pigeonhole principle. Experience with invariants and the extremal principle is also helpful.
EDIT: CHAPTER 9 IS OUT! Since only 3 attachments are allowed per post, I have uploaded chapters 4, 5 and 6 in my comment below (10th on this page), and chapters 7, 8, and 9 further below (comment number 49 on this page).
NOTE: The solution to example 8 in chapter 1 is incorrect, and will be corrected in the final version of the book. For now, ignore this example.

Full book (uploaded by green_dog_7983): Dead Link
[Amir: new link]
126 replies
Pascal96
Aug 6, 2014
zaahir
Dec 27, 2023
Olympiad Combinatorics Book
G H J
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pascal96
124 posts
#1 • 457 Y
Y by bcp123, Konigsberg, gobathegreat, utkarshgupta, frill, sabbasi, professordad, rgreenanswers, AndrewKwon97, thkim1011, PatrikP, fclvbfm934, happiface, fireonice18, El_Ectric, TheCrafter, minimario, shivangjindal, Cyclicduck, raptorw, sicilianfan, misgiven, tau172, ABCDE, wcao9311, CalcCrunch, TheMaskedMagician, acupofmath, Wawowiee, debjit1999, Em80, socrates, Boomer, Amir Hossein, AnonymousBunny, Ashutoshmaths, ThePathOfWar, mbrc, Philip7086, flamefoxx99, NormanWho, Chaos_Theory, Uagu, RishabhDahale, Anish_S, RadioActive, explogabloger, hnhuongcoi, ARCH999, kenneth102099, Debdut, Kezer, blippy1998, DominicanAOPSer, mihajlon, Higgsboson79, rigor, AdithyaBhaskar, drkim, 24iam24, DrMath, sheripqr, ATimo, ssk9208, champion999, AdBondEvent, huricane, trumpeter, Wave-Particle, joey8189681, amplreneo, yojan_sushi, shinichiman, aops777, hwl0304, Eugenis, bearytasty, pican, FTW, nikolapavlovic, fractals, Rubaiya, NHN, Tintarn, randomusername, InCtrl, anantmudgal09, MathPanda1, Knin2820, yimingz89, GoJensenOrGoHome, monkeyl, SHARKYBOY, quantummath, WOOT2016er, rkm0959, Devesh14, TheOneYouWant, mathtastic, simos20, quangminhltv99, Hydrogen-Helium, madmathlover, K6160, tarzanjunior, Ankoganit, mewtwomew, jam10307, lucasxia01, m1234567, brianapa, pinetree1, fireclaw105, NTA1907, babu2001, shiningsunnyday, mathwizard888, ankitsnigam, dtxiong, stan23456, Plasma_Vortex, Generic_Username, wu2481632, mrowhed, Temp456, rterte, DeathLlama9, Flash12, andrei_cdr29, gradysocool, purpleapples, always_correct, nsato, 62861, Natsu_Dragneel, skys, math90, pi_Plus_45x23, Snowfractals, Number1, Vietnamisalwaysinmyheart, Churent, thunderz28, JasperL, mathcrazymj, rafayaashary1, MathSlayer4444, Phie11, steppewolf, tenplusten, vsathiam, Swag00, TYERI, tiwarianurag021999, Weakinmath, bluephoenix, Problem_Penetrator, kk108, user2324335345, shawnee03, claserken, div5252, Kayak, nmd27082001, Gh324, Sids2k, ThisIsASentence, ArijitViswananthan, targo___, samuel, fatant, rodamaral, Tawan, AnArtist, QWERTYphysics, dram, enhanced, ccx09, 277546, Uros, integrated_JRC, tapir1729, NotKris, Kagebaka, Wizard_32, Vrangr, rmtf1111, Zoom, opplakat, e_plus_pi, lifeisgood03, taisan, lazysnorlax, MNJ2357, Supercali, mathlogician, samoha, gmail.com, Durjoy1729, illogical_21, MEGAKNIGHT, ultralako, allinnohesitation, InfiniteAnswers, AlastorMoody, TheMagician, math-o-enthu, bhargav13baruah13, biomathematics, NOLF, mathisreal, Aspirant-to-IMO, niyu, Arhaan, Saikat002, Drunken_Master, Mathisfun04, doitsudoitsu, nikhil.mudumbi, BinomialMoriarty, magicarrow, MathInfinite, TheDarkPrince, sriraamster, MathbugAOPS, AbsoluteZer0, aadhitya, Twistya, PhysicsMonster_01, MathPassionForever, SoumikNayak, RAMUGAUSS, NoDealsHere, TheCoolDinosuar, mathleticguyyy, Guardiola, Mathotsav, Math_Is_Life_03, Spiralflux789, Vietjung, MelonGirl, Math-wiz, FISHMJ25, meet18, MathematicalPhysicist, Systematicworker, p_square, duttaditya18, hellomath010118, Varuneshwara, Kaisun, fjm30, Atpar, lilavati_2005, heidi3003, Loppukilpailija, Aarth, GeronimoStilton, SHREYAS333, Greenleaf5002, whatRthose, Sumgato, Polipo2704, mathsworm, WindTheorist, BigSams, khina, Feridimo, Martin007B, ErijonHasi1, yaseenmollik, Bassiskicking, RudraRockstar, Gumnaami_1945, amar_04, Math_olympics, Kamran011, freeman66, Toinfinity, a2048, tree_3, OlympusHero, Zorger74, AmirKhusrau, Dem0nfang, The_Conjecturer, mueller.25, MintTea, Bltbob, tastymath75025, Aspiring_Mathletes, Kanep, Abbas11235, The_Giver, char2539, adityaguharoy, Purple_Planet, Orangensaft12, CaptainLevi16, khan.academy, NePtUnEMaTh, smartkmd1, matinyousefi, TwilightZone, Aryan-23, scimaths, Kgxtixigct, myh2910, Yusrizal, Han1728, Imayormaynotknowcalculus, Awesome_guy, Googolplexian, heheXD1, leibnitz, ghu2024, Gaussian_cyber, Pluto1708, Invert_DOG_about_centre_O, PROA200, Bumblebee60, ilovepizza2020, Nathanisme, itslumi, A-Thought-Of-God, Congruentisogonal44, DievilOnlyM, A_Math_Lover, NJOY, IAmTheHazard, captainsnake, Talgat05, Pitagar, Geo_alphan, anonman, TsunamiStorm08, Didier, lazybean123, ProblemSolver2048, Hamroldt, babygrogu, Ucchash, k12byda5h, MathsMadman, tigerzhang, Euler1728, 606234, phoenixfire, EmilXM, Aritra12, Ninjasolver0201, Rg230403, superagh, Andrei246, IceWolf10, sotpidot, NumberX, EllipticSWAN, samrocksnature, EZmath2006, Jerry122805, hakN, Siddharth03, 554183, Wizard0001, srijonrick, parmenides51, N1RAV, mathlearner2357, MathJams, Taco12, NealShrestha, abvk1718, violin21, megarnie, Nymoldin, guavaSeabird, john0512, sklf023, Timmy456, IMUKAT, Elnuramrv, Flying-Man, TheCollatzConjecture, Pranav1056, CyclicISLscelesTrapezoid, Superguy, AwesomeYRY, MrOreoJuice, Sprites, Hexagon_6-, Nuterrow, ALM_04, pikapika007, polynomialian, rayfish, skyguy88, Seicchi28, wasikgcrushedbi, Gacac, Jndd, Miku_, DPS, PHSH, HamstPan38825, mathking999, Zaro23, Blast_S1, a-dumb-math-kid, rama1728, Quidditch, somebodyyouusedtoknow, Mathlover_1, David-Vieta, sehgalsh, userr.7, matharcher, Mogmog8, adorefunctionalequation, howcanicreateacccount, thepigod762, GeoKing, EpicBird08, ab2024, huashiliao2020, peelybonehead, s12d34, Rainmaker2627, wenwenma, Adventure10, Mango247, cursed_tangent1434, Tafi_ak, johnlee1234, anonymouzzz, ATGY, TestX01, ohiorizzler1434, ehuseyinyigit, Lhaj3, Fah2008, fearsum_fyz, cubres, Victor14209, and 13 other users
Hi everyone, I am currently writing a book on combinatorics for people preparing for national and international math competitions, especially the IMO and selection tests leading up to it. The book is intended to expose readers to a variety of ideas, techniques and problem solving strategies, ranging from the intuitive “greedy algorithms” in the first chapter to the powerful Probabilistic Method in chapter nine.
I am uploading chapter one here, and would appreciate your feedback and any suggestions. Over the coming weeks, I will be uploading the remaining chapters one at a time.
The only prerequisites are familiarity with basic graph theoretic concepts and terminology, algebraic inequalities, induction and the pigeonhole principle. Experience with invariants and the extremal principle is also helpful.
EDIT: CHAPTER 9 IS OUT! Since only 3 attachments are allowed per post, I have uploaded chapters 4, 5 and 6 in my comment below (10th on this page), and chapters 7, 8, and 9 further below (comment number 49 on this page).
NOTE: The solution to example 8 in chapter 1 is incorrect, and will be corrected in the final version of the book. For now, ignore this example.

Full book (uploaded by green_dog_7983): Dead Link
[Amir: new link]
Attachments:
OlympiadCombinatoricsChapter1.pdf (869kb)
OlympiadCombinatoricsChapter2.pdf (814kb)
OlympiadCombinatoricsChapter3.pdf (924kb)
This post has been edited 15 times. Last edited by Amir Hossein, Jan 23, 2020, 7:55 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
utkarshgupta
2280 posts
#2 • 6 Y
Y by Pascal96, Math_olympics, samrocksnature, Adventure10, cubres, and 1 other user
Thanx a lot !!!!!!

That is exactly what I need !

I will be eagerly waiting for subsequent chapters !!!!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Konigsberg
2239 posts
#3 • 12 Y
Y by droid347, mathcrazymj, dram, Math_olympics, samrocksnature, IceWolf10, Adventure10, Mango247, cubres, and 3 other users
I would be reading the first chapter when I have time, but a quick glance to me says that it is quite good. It seems a good (combinatorial) counterpart to v_Enhance's geometry book. Will there be solutions to the exercise problems, or we have to search them ourselves?

May I ask when would the other chapters be posted?

Thanks!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pascal96
124 posts
#4 • 10 Y
Y by mathcrazymj, hibiscus, samuel, Math_olympics, samrocksnature, Adventure10, Mango247, cubres, and 2 other users
Thank you for your positive feedback! To answer your questions, there may be a gap of about a week before I put up the next chapter since I will be out of town, but after that I should be putting up two to three per week. There will be nine chapters in total, covering algorithms (two chapters), processes, existence, games, counting in two ways, extremal combinatorics, graph theory and the probabilistic method. Eventually I will put them all into a single, complete pdf with a brief appendix on prerequisites as well. I thought I would initially post chapters individually to get some feedback and make changes where required.
As of now I do not have any plans to write solutions to exercise problems, but if you would like a hint/solution sketch to a particular problem you have been working on feel free to pm me. It may also be useful to know that the exercises are (for the most part) arranged in increasing order of difficulty (with exercise 10 being an exception as it is a lemma needed for 11).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
deepesh
59 posts
#5 • 5 Y
Y by blackwave, Math_olympics, samrocksnature, Adventure10, cubres
I cant find the link for some reason
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
utkarshgupta
2280 posts
#6 • 5 Y
Y by Math_olympics, samrocksnature, Adventure10, Mango247, cubres
Maybe you are on a tab or mobile
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Konigsberg
2239 posts
#7 • 5 Y
Y by Math_olympics, samrocksnature, Adventure10, Mango247, cubres
could you give links for the solutions to the informatics olympiad problems? the others could be found either through google or aops resources.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pascal96
124 posts
#8 • 4 Y
Y by Math_olympics, samrocksnature, Adventure10, cubres
Most of them should be under greedy algorithms at this link: http://www.iarcs.org.in/inoi/online-study-material/topics/
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Konigsberg
2239 posts
#9 • 5 Y
Y by Math_olympics, samrocksnature, Adventure10, Mango247, cubres
oh ok. When would the other chapters be posted?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pascal96
124 posts
#10 • 5 Y
Y by Math_olympics, samrocksnature, Adventure10, cubres, and 1 other user
I just uploaded chapter 2. Chapters 3, 4 and 5 should be ready within the next 3 or 4 days
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pascal96
124 posts
#11 • 30 Y
Y by bcp123, fclvbfm934, PatrikP, acupofmath, hungrycap, RishabhDahale, RadioActive, ARCH999, huricane, trumpeter, bearytasty, pican, TheOneYouWant, 62861, thunderz28, e_plus_pi, samuel, mathrabbit812, allinnohesitation, Math_olympics, Pluto1708, samrocksnature, Adventure10, EpicBird08, cubres, and 5 other users
It turns out I'm only allowed 3 attachments in one post, so here are chapters 4 and5.
EDIT: Chapter 6 is out!
Attachments:
OlympiadCombinatoricsChapter4.pdf (867kb)
Chapter5 Games Aug 2014.pdf (801kb)
Chapter6 Aug 2014.pdf (884kb)
This post has been edited 2 times. Last edited by Pascal96, Sep 4, 2014, 12:15 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thkim1011
3135 posts
#12 • 4 Y
Y by samrocksnature, Adventure10, cubres, and 1 other user
Thank you! I hardly know any olympiad combinatorics, so I guess this is a good chance to learn. Just wondering, what did you use to write this book?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mentalgenius
1020 posts
#13 • 5 Y
Y by Math_olympics, samrocksnature, Adventure10, cubres, and 1 other user
It looks like Microsoft Word.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6882 posts
#14 • 38 Y
Y by butter67, zmyshatlp, Pascal96, bearytasty, TheOneYouWant, madmathlover, CQYIMO42, CeuAzul, mcmcphie, mathcrazymj, samuel, mathrabbit812, Spiralflux789, lemon94, RudraRockstar, Math_olympics, Pi-is-3, myh2910, amar_04, Nathanisme, Euler1728, samrocksnature, primesarespecial, Thapakazi, abvk1718, Hypatia1728, weili4216, rayfish, AOPSUser2357, EpicBird08, Adventure10, NicoN9, fearsum_fyz, Rounak_iitr, cubres, and 3 other users
This work is really impressive! You are very fast.

Here are some comments as I read through the first chapter. Most of these are just little nitpicks and may not be worth weighting very heavily. The stuff I believe more firmly is in italics. If you want to discuss more, you are welcome to email me at $\text{evanchen}@\text{mit.edu}$.

Introduction
Second paragraph: "Often an algorithm can ... field of number theory". This feels like "fluff" to me, doesn't contribute much to the paragraph and the first sentence seems vacuously true. Also not sure how much I agree with the claim that the Euclidean algorithm is the basis of NT, but that's beside the point ;)

Third paragraph: Perhaps you might want to put this in a preface / chapter 0 of some sort.

Greedy Algorithms
Nice quote :)

"in each step" might be better as "at each step"

"They aren't always the optimal algorithm in the long run" is kind of awkward and "they" seems not so well-defined.
I suggest "Greedy algorithms are not always optimal in the long run".

Example 1
Solution: You may prefer to use $c_1$, $c_2$, for colors and $v_1$, $v_2$, for vertices.

Remark: This is good. You might also want to note something to the effect that the greedy algorithms are also _dumb_; they don't take a lot of things into account. To illustrate this point, you might mention Brook's Theorem, which shows that $\Delta +1$ is usually not tight. I think it's useful to point out in this way that the greedy algorithm usually does not always perform optimally.

Example 2
The comment about how the trivial greedy algorithm fails is IMO very good. I don't know why so few books make comments like this.
Actually the entire solution is just very well-explained.

And that remark at the end about boring calculations is hilarious. Please keep it!

Example 3
You might be pushing a little here with the amount of graph theory to assume, but that's probably fine.
You should mention that $H$ must be nonempty.
Is there a missing space between "$V$" and "vertices" in the problem statement?

The solution feels a bit more dense here than the preceding solutions. Some paragraph breaks might help, at least.
Moreover, I think the wording in terms of edges/vertices instead of average degree is both confusing and counterintuitive (at one point, I thought that the value of $E$ and $V$ were changing). I think the following phrasing might be more intuitive:
"If $d$ is the average degree, then we want to delete vertices until the minimum degree is at least $d/2$.
Call a vertex bad if the degree is less than $d/2$, and begin deleting bad vertices arbitrarily.
... more text ...
Notice that as we delete bad vertices, the average degree of the graph increases, because BLAH "
and then proceed to show the resulting $H$ is nonempty. At the very least, I don't think the "(it started as $E/V$ ...)" should be stuffed into a parenthetical.

Is the bound $d/2$ tight? I feel like looking at a case where equality occurs would be useful for understanding what is happening.
Actually I can't tell from reading your solution why $d/2$ can't be replaced by something else, so I think you should definitely elaborate on why the average degree is strictly increasing.

Example 4
Let $a=1776$ seems more conventional than $1776=a$. Also, spacing issues. Would appreciate a paragraph break after "call these small sets and big sets respectively".

The explanation of heuristics is very good here in my opinion. So is the remark at the end.

"Suppose the algorithm fails (that is ..." -- Again, I object to the stuffing of content in parentheses, though not quite as strongly as the previous issue.

Invariants / Monovariants
"... and an invariant is quantity that doesn't change." maybe append "at all" to the end of this sentence.
You might also like to talk briefly about how monovariants / invariants are used, namely
(i) monovariants are often used to show that some process terminates, and
(ii) invariants are often used to show that some state cannot be achieved.

Example 5
How would you think of the black/white coloring?

"... making all but the last 2 entries 0 ..." use "two" instead of "2".

Example 6
Oh man this is a really good example problem. You might want to explain more towards the beginning that we choose the weights in such a way that passing towards $A_0$ does not change the sum of the weights.

The $W_+$ and $W_-$ is actually tricky, initially I thought that $A_n$ could just pass in either direction and it would still work. You might want to show explicitly that this is not the case -- that is, explain why $A_n$ actually needs to be careful by showing an example where $A_n$ passes the wrong way and everyone is sad, then go into the $W_+$ and $W_-$ distinction.

Example 7
"The second part of the question is trivial" -- I think a little more here would be appreciated. It would probably be sufficient to add something of the form "the sum of the money is invariant".

Example 8
I'm not thinking very well right now, but why is this algorithm optimal? You have this $X$ which decreases by $1$ for most transfers, but decreases by more if one transfers from $n$ to $1$. But the "full algorithm" you specified involves doing the second operation whenever possible; in other words, greedily. Why is that sufficient?

Example 9
"Let the sum of a position ... maximum of the 6 numbers" The wording is a bit clumsy here.
Maybe you want "Let the sum and maximum of a position denote the sum and maximum, respectively, of the six numbers".
And again you may want to use "six" instead of "6".

The explanation of the sub-algorithms is good. Some diagrams might be appreciated.

Misc
At this point my mom is telling me I'm going to a doctor appointment soon, so I'm just skimming now.
The fact that I can still pick up the main idea of the solution is a very positive sign.

Example 10
Nitpick: you ought to be consistent with your (a), (b), (c), (d), since you use double-parens (b) for the label but single-parens b) in the main text.

However, I think your dissection into the (a), (b), (c), (d) observations is very, very good.

Example 11
Now you have a), b), c), d) in the labels. Again, you should try and be consistent.

The prose is very clear though. Again, you motivate the solution very well.

The remark is quite good. I recall being surprised at the low scores for the Problem 6 that year until I remembered what Problem 5 was.
Deputy leaders too good :P

Example 12
The notation here is really dense. Diagrams would be really helpful here, especially for a problem this difficult.

Exercises
The mixture with CS algorithm flavoring is interesting; I personally like it but don't know if others will. It might be worth defining stuff like $O(n^2)$ so that you don't have to keep repeating yourself now or later.

Problem 4 is from some Putnam, but I don't remember which year. It's possible that Putnam stole it though.

You might be interested in providing hints to the problems: just one or two sentences that outlines the main idea. I can attest that this takes much, much less time than writing full solutions, and has a similarly useful effect.

That's all for now, will write more later. And again, feel free to email me if you want to follow up on anything.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pascal96
124 posts
#15 • 19 Y
Y by Eugenis, mathcrazymj, Problem_Penetrator, samuel, RudraRockstar, Math_olympics, Pi-is-3, Nathanisme, samrocksnature, Adventure10, Mango247, winniep008hfi, NicoN9, cubres, and 5 other users
Thank you for all your detailed advice Evan. I'll definitely make the relevant changes in the final book. I agree with all of it apart from a few points.
Introduction: The sentences "Often an algorithm... field of number theory" are intended to contrast with the first paragraph. While the first paragraph asserts that algorithms have several "external" uses - uses outside of mathematics - the second paragraph indicates that the focus of this chapter will be to use algorithms as tools to solve mathematical problems. In fact, I do not think it is that obvious that existence problems like example 3 and 4 can be solved by designing algorithms. Perhaps I should reword these sentences a little to make this clearer.
Example 3: No there's no space missing. It just looks like that because of the italics. But I agree with your other remarks about this problem.
Invariants/monovariants: In the final book there will be a chapter introducing some prerequisites, which will define invariants and monovariants, and also introduce the idea of black and white colorings.
Example 7: Isn't it clear that the total money is invariant? He can only transfer money between accounts, not make or destroy money.
Exercises: I agree with what you said about the "CS algorithm flavoring". Do you think I should put these into a separate section at the end? Also, I think problems 7, 9, 10 and 11 are okay since no algorithm design is required, only analysis.
Z K Y
G
H
=
a