Plan ahead for the next school year. Schedule your class today!

G
Topic
First Poster
Last Poster
k a July Highlights and 2025 AoPS Online Class Information
jwelsh   0
Jul 1, 2025
We are halfway through summer, so be sure to carve out some time to keep your skills sharp and explore challenging topics at AoPS Online and our AoPS Academies (including the Virtual Campus)!

[list][*]Over 60 summer classes are starting at the Virtual Campus on July 7th - check out the math and language arts options for middle through high school levels.
[*]At AoPS Online, we have accelerated sections where you can complete a course in half the time by meeting twice/week instead of once/week, starting on July 8th:
[list][*]MATHCOUNTS/AMC 8 Basics
[*]MATHCOUNTS/AMC 8 Advanced
[*]AMC Problem Series[/list]
[*]Plus, AoPS Online has a special seminar July 14 - 17 that is outside the standard fare: Paradoxes and Infinity
[*]We are expanding our in-person AoPS Academy locations - are you looking for a strong community of problem solvers, exemplary instruction, and math and language arts options? Look to see if we have a location near you and enroll in summer camps or academic year classes today! New locations include campuses in California, Georgia, New York, Illinois, and Oregon and more coming soon![/list]

MOP (Math Olympiad Summer Program) just ended and the IMO (International Mathematical Olympiad) is right around the corner! This year’s IMO will be held in Australia, July 10th - 20th. Congratulations to all the MOP students for reaching this incredible level and best of luck to all selected to represent their countries at this year’s IMO! Did you know that, in the last 10 years, 59 USA International Math Olympiad team members have medaled and have taken over 360 AoPS Online courses. Take advantage of our Worldwide Online Olympiad Training (WOOT) courses
and train with the best! Please note that early bird pricing ends August 19th!
Are you tired of the heat and thinking about Fall? You can plan your Fall schedule now with classes at either AoPS Online, AoPS Academy Virtual Campus, or one of our AoPS Academies around the US.

Our full course list for upcoming classes is below:
All classes start 7:30pm ET/4:30pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
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
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
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
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
Sunday, Oct 19 - Jan 25
Tuesday, Nov 4 - Feb 10
Sunday, Dec 7 - Mar 8

Introduction to Number Theory
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
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, 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!)
Sat & Sun, Sep 13 - Sep 14 (1:00 - 4:00 PM PT/4:00 - 7:00 PM ET)

Intermediate: Grades 8-12

Intermediate Algebra
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, Sep 28 - Feb 15
Tuesday, Nov 4 - Mar 24

Intermediate Number Theory
Wednesday, Sep 24 - Dec 17

Precalculus
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

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

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
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
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
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
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
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
Tuesday, Sep 2 - Nov 18

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

Intermediate Programming with Python
Friday, Oct 3 - Jan 16

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

Physics

Introduction to Physics
Tuesday, Sep 2 - Nov 18
Sunday, Oct 5 - Jan 11
Wednesday, Dec 10 - Mar 11

Physics 1: Mechanics
Sunday, Sep 21 - Mar 22
Sunday, Oct 26 - Apr 26
0 replies
jwelsh
Jul 1, 2025
0 replies
k i Suggestion Form
jwelsh   0
May 6, 2021
Hello!

Given the number of suggestions we’ve been receiving, we’re transitioning to a suggestion form. If you have a suggestion for the AoPS website, please submit the Google Form:
Suggestion Form

To keep all new suggestions together, any new suggestion threads posted will be deleted.

Please remember that if you find a bug outside of FTW! (after refreshing to make sure it’s not a glitch), make sure you’re following the How to write a bug report instructions and using the proper format to report the bug.

Please check the FTW! thread for bugs and post any new ones in the For the Win! and Other Games Support Forum.
0 replies
jwelsh
May 6, 2021
0 replies
k i Read me first / How to write a bug report
slester   3
N May 4, 2019 by LauraZed
Greetings, AoPS users!

If you're reading this post, that means you've come across some kind of bug, error, or misbehavior, which nobody likes! To help us developers solve the problem as quickly as possible, we need enough information to understand what happened. Following these guidelines will help us squash those bugs more effectively.

Before submitting a bug report, please confirm the issue exists in other browsers or other computers if you have access to them.

For a list of many common questions and issues, please see our user created FAQ, Community FAQ, or For the Win! FAQ.

What is a bug?
A bug is a misbehavior that is reproducible. If a refresh makes it go away 100% of the time, then it isn't a bug, but rather a glitch. That's when your browser has some strange file cached, or for some reason doesn't render the page like it should. Please don't report glitches, since we generally cannot fix them. A glitch that happens more than a few times, though, could be an intermittent bug.

If something is wrong in the wiki, you can change it! The AoPS Wiki is user-editable, and it may be defaced from time to time. You can revert these changes yourself, but if you notice a particular user defacing the wiki, please let an admin know.

The subject
The subject line should explain as clearly as possible what went wrong.

Bad: Forum doesn't work
Good: Switching between threads quickly shows blank page.

The report
Use this format to report bugs. Be as specific as possible. If you don't know the answer exactly, give us as much information as you know. Attaching a screenshot is helpful if you can take one.

Summary of the problem:
Page URL:
Steps to reproduce:
1.
2.
3.
...
Expected behavior:
Frequency:
Operating system(s):
Browser(s), including version:
Additional information:


If your computer or tablet is school issued, please indicate this under Additional information.

Example
Summary of the problem: When I click back and forth between two threads in the site support section, the content of the threads no longer show up. (See attached screenshot.)
Page URL: http://artofproblemsolving.com/community/c10_site_support
Steps to reproduce:
1. Go to the Site Support forum.
2. Click on any thread.
3. Click quickly on a different thread.
Expected behavior: To see the second thread.
Frequency: Every time
Operating system: Mac OS X
Browser: Chrome and Firefox
Additional information: Only happens in the Site Support forum. My tablet is school issued, but I have the problem at both school and home.

How to take a screenshot
Mac OS X: If you type ⌘+Shift+4, you'll get a "crosshairs" that lets you take a custom screenshot size. Just click and drag to select the area you want to take a picture of. If you type ⌘+Shift+4+space, you can take a screenshot of a specific window. All screenshots will show up on your desktop.

Windows: Hit the Windows logo key+PrtScn, and a screenshot of your entire screen. Alternatively, you can hit Alt+PrtScn to take a screenshot of the currently selected window. All screenshots are saved to the Pictures → Screenshots folder.

Advanced
If you're a bit more comfortable with how browsers work, you can also show us what happens in the JavaScript console.

In Chrome, type CTRL+Shift+J (Windows, Linux) or ⌘+Option+J (Mac).
In Firefox, type CTRL+Shift+K (Windows, Linux) or ⌘+Option+K (Mac).
In Internet Explorer, it's the F12 key.
In Safari, first enable the Develop menu: Preferences → Advanced, click "Show Develop menu in menu bar." Then either go to Develop → Show Error console or type Option+⌘+C.

It'll look something like this:
IMAGE
3 replies
slester
Apr 9, 2015
LauraZed
May 4, 2019
k i Community Safety
dcouchman   0
Jan 18, 2018
If you find content on the AoPS Community that makes you concerned for a user's health or safety, please alert AoPS Administrators using the report button (Z) or by emailing sheriff@aops.com . You should provide a description of the content and a link in your message. If it's an emergency, call 911 or whatever the local emergency services are in your country.

Please also use those steps to alert us if bullying behavior is being directed at you or another user. Content that is "unlawful, harmful, threatening, abusive, harassing, tortuous, defamatory, vulgar, obscene, libelous, invasive of another's privacy, hateful, or racially, ethnically or otherwise objectionable" (AoPS Terms of Service 5.d) or that otherwise bullies people is not tolerated on AoPS, and accounts that post such content may be terminated or suspended.
0 replies
dcouchman
Jan 18, 2018
0 replies
Sum of GCD
Timta27   1
N 8 minutes ago by alexheinis
Source: own
Prove that there are infinitely many integers $k,$ so for any integer $n$, where $3 \leq k+2 \leq n$, it is possible to find three natural numbers $a,b,c$ ($k \leq a \leq b \leq c <n $) such that $GCD(a,b)+GCD(a,c)+GCD(b,c) = n$.
1 reply
Timta27
3 hours ago
alexheinis
8 minutes ago
nice inequality by panaitopol
manlio   88
N 20 minutes ago by mudkip42
Source: JBMO 2002, Problem 4
Prove that for all positive real numbers $a,b,c$ the following inequality takes place
\[ \frac{1}{b(a+b)}+ \frac{1}{c(b+c)}+ \frac{1}{a(c+a)} \geq \frac{27}{2(a+b+c)^2} . \]
Laurentiu Panaitopol, Romania
88 replies
manlio
Sep 21, 2003
mudkip42
20 minutes ago
Forgotten coaxiality lemma and more
Vivouaf   4
N 22 minutes ago by aqwxderf
Source: self discovered
Let $\omega_1$, $\omega_2$ be two circles. We define for a point $X$ in the plane $\mathbb{P}_{\omega}(X)$ to be the power of $X$ wrt to circle $\omega$.
- Prove that the locus of points $X$ such that $\frac{\mathbb{P}_{\omega_1}(X)}{\mathbb{P}_{\omega_2}(X)} = K$ for some real constant $K$ is a circle coaxial to $\omega_1$ and $\omega_2$, which will be denoted by $S_K$.
- Prove that the center $O_K$ of $S_K$, $O_1$ of $\omega_1$, and $O_2$ of $\omega_2$ are such that $\frac{\overline{O_KO_1}}{\overline{O_KO_2}} = K$
4 replies
Vivouaf
Today at 8:45 AM
aqwxderf
22 minutes ago
Grid with consecutive entries
MarkBcc168   17
N 40 minutes ago by monval
Source: ELMO 2020 P5
Let $m$ and $n$ be positive integers. Find the smallest positive integer $s$ for which there exists an $m \times n$ rectangular array of positive integers such that
[list]
[*]each row contains $n$ distinct consecutive integers in some order,
[*]each column contains $m$ distinct consecutive integers in some order, and
[*]each entry is less than or equal to $s$.
[/list]

Proposed by Ankan Bhattacharya.
17 replies
1 viewing
MarkBcc168
Jul 28, 2020
monval
40 minutes ago
Processing module python not working
Demetri   11
N Jul 8, 2025 by PikaPika999
The following code doesn't work, because canvas isn't implemented for the processing module:
import processing
def setup():
    processing.size(200, 200)
def draw():
    processing.ellipse(100, 100, 50, 50)
    processing.noLoop()
processing.run()

I believe this is an easy fix, someone just forgot to add the line "Sk.canvas = outcanvas;"(or something similar) in the code for the pywindow, which would give an output.
11 replies
Demetri
Jul 1, 2025
PikaPika999
Jul 8, 2025
k Cannot post PHP
char0221   7
N Jul 8, 2025 by huolongguo10
Summary of the problem: If I try to post anything with PHP (a coding language), it
Page URL: In any forum or private messages
Steps to reproduce:
1. Create a post.
2. Put some PHP inside, can't give example
Expected behavior: Should post the message
Frequency: 100%
Operating system(s): macOS Sequoia 15.2.1
Browser(s), including version: Safari
Additional information: See attachments
7 replies
char0221
Apr 30, 2025
huolongguo10
Jul 8, 2025
k AoPS Wiki being really slow
SwordAxe   2
N Jul 8, 2025 by SwordAxe
Summary of the problem: AoPS wiki is being really slow, when I'm loading up amc 10 questions it takes around 30 seconds to load, but other parts of the site aren't slow
Page URL: aopswiki
Steps to reproduce:
1. go onto aops wiki and searh an amc 10 question or any type of question or page

Expected behavior: being slow
Frequency: almost always, sometimes it loads fast
Operating system(s): Windows 10
Browser(s), including version: newest microsoft edge
Additional information:
2 replies
SwordAxe
Jul 8, 2025
SwordAxe
Jul 8, 2025
PAGE NOT SCROLLING DOWN ALL THE WAY; GETS STUCK 1.5 POSTS BEFORE THREAD END
CurlyFalcon55   31
N Jul 8, 2025 by PikaPika999
Summary of the problem:
Whenever I push the big, top right "Reply" button– NOT THE SMALL LITTLE "QUICK REPLY" BAR ON THE BOTTOM, and reply, I can't scroll down all the way to the bottom of the thread that I just posted in. Sometimes, very rarely though, I doesn't scroll down all the way when I push the "Quick Reply" bar.


-----Page URL:
Anywhere in the "Introduction to Number Theory" forum in AoPS


-----Steps to reproduce:

1. Go to the link above.

2. Click any thread or create a new one.

3. Click the "Reply" button, not the quick reply bar.

4. Type a reply.

5. Push the "Submit" button.

6. Try to scroll down. if you’re lucky, the problem will reproduce.

-----Expected behavior:
To scroll all the way down.


-----Frequency:
Almost every time I push the big "Reply" button, sometimes (but rarely) when I push the "Quick Reply" bar.


-----Operating system(s):
macOS Sequoia 15.4.1


-----Browser(s), including version:
Chrome, (I don't know what version)


-----Additional information:
-It rarely does it in the "Quick Reply" bar.
-It almost always does it in the big "Reply" button on the top right.


-----Can anyone reproduce?
31 replies
CurlyFalcon55
Jun 1, 2025
PikaPika999
Jul 8, 2025
k I can't type into boxes during lessons
HADP   7
N Jul 7, 2025 by jlacosta
Recently, I have been experiencing an issue where i can't type into the boxes that professors post during a lesson. I can't input an answer and i've tried refreshing multiple times and it doesn't work. This has happened in many lessons in a row. Please help! Also, is there a way to make Aops dark mode?
7 replies
HADP
Jul 1, 2025
jlacosta
Jul 7, 2025
k Happy 4th of July!!!
pingpongmerrily   207
N Jul 7, 2025 by pingpongmerrily
AoPS is taking classes off for it, so I think we should celebrate it...
[rule]
[center]IMAGE
[rule]
:trampoline: Happy 4th of July!!!
207 replies
pingpongmerrily
Jul 4, 2025
pingpongmerrily
Jul 7, 2025
k Just so SS knows....
jmr2010   10
N Jul 7, 2025 by CuriousMathBoy72
If you open a PM, specify yourself, and put something there, then hit send, it says you are automatically included and if you want to talk to yourself, leave the to box blank. If you leave the box blank, it won't send the PM because the to box is blank
10 replies
jmr2010
Jul 2, 2025
CuriousMathBoy72
Jul 7, 2025
k I've been wrongfully disabled
K124659   5
N Jul 5, 2025 by K124659
Summary of the problem: My alcumus account has been "banned"
Page URL: Anywhere on alcumus
Steps to reproduce (I reccomend you don't):
1. Answer questions extremely quickly whilst spamming the enter button
Expected behavior: You'll get banned. I believe this is some sort of system to disable bots.
Frequency: I'm not sure.
Operating system(s): Acer 311 Chromebook
Browser(s), including version: Google Chrome
Additional information: I believe this is due to the fact that I knew most of the questions either by heart or because they are extremely easy (It was multiplying fractions in pre-algebra that got me banned), and as a result I was going too fast and was spamming inputs into the system, similar to a bot. I wasn't using a bot, however. I'm not even grinding HOF- I had broken record as a quest with my problem streak being 399 previously, so my usage of the same subject to get a bunch correct was lowk necessary ngl.
5 replies
K124659
Jul 5, 2025
K124659
Jul 5, 2025
k Searching for keywords
Cats_on_a_computer   1
N Jul 4, 2025 by Demetri
Quick question because I’m new here, I keep searching keywords in the community search functions to check if they’ve been posted before, and every time it ended up not finding the original, leading to a repost. This has happened so many times I’ve decided not to post anymore until I can somehow find a way to efficiently search for it.
I accidentally reposted a Putnam 2006, even though I searched for the keywords in the question, but since I didn’t know it was a Putnam problem (I had seen it somewhere else), I didn’t manage to find the problem so unknowingly reposted it.
1 reply
Cats_on_a_computer
Jul 4, 2025
Demetri
Jul 4, 2025
k REQUEST LOCK
KangarooPrecise   25
N Jul 3, 2025 by ahxun2006
On my username, why is there 3 dots after it, when 2 letters are missing?
25 replies
KangarooPrecise
Jul 2, 2025
ahxun2006
Jul 3, 2025
Graph Process Problem
Maximilian113   15
N Jun 13, 2025 by heheman
Source: CMO 2025 P1
The $n$ players of a hockey team gather to select their team captain. Initially, they stand in a circle, and each person votes for the person on their left.

The players will update their votes via a series of rounds. In one round, each player $a$ updates their vote, one at a time, according to the following procedure: At the time of the update, if $a$ is voting for $b,$ and $b$ is voting for $c,$ then $a$ updates their vote to $c.$ (Note that $a, b,$ and $c$ need not be distinct; if $b=c$ then $a$'s vote does not change for this update.) Every player updates their vote exactly once in each round, in an order determined by the players (possibly different across different rounds).

They repeat this updating procedure for $n$ rounds. Prove that at this time, all $n$ players will unanimously vote for the same person.
15 replies
Maximilian113
Mar 7, 2025
heheman
Jun 13, 2025
Graph Process Problem
G H J
G H BBookmark kLocked kLocked NReply
Source: CMO 2025 P1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
587 posts
#1
Y by
The $n$ players of a hockey team gather to select their team captain. Initially, they stand in a circle, and each person votes for the person on their left.

The players will update their votes via a series of rounds. In one round, each player $a$ updates their vote, one at a time, according to the following procedure: At the time of the update, if $a$ is voting for $b,$ and $b$ is voting for $c,$ then $a$ updates their vote to $c.$ (Note that $a, b,$ and $c$ need not be distinct; if $b=c$ then $a$'s vote does not change for this update.) Every player updates their vote exactly once in each round, in an order determined by the players (possibly different across different rounds).

They repeat this updating procedure for $n$ rounds. Prove that at this time, all $n$ players will unanimously vote for the same person.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
587 posts
#2
Y by
bruh
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1780 posts
#3
Y by
Solution Sketch:

The idea is that there is this "center cycle" that will persist until it becomes a self-loop. Each time a member of the center cycle changes vote, the center cycle's size decreases by 1. One can find that this means that each time the procedure is run through, the center cycle decreases by at least half. This will take $\lfloor \log_2(n)\rfloor$

After that, we can consider distances to that self-loop. Each individual path decreases in a way very similar to that cycle we mentioned earlier, and so the worst case scenario is that the path size is $n-1$, whence it will take $\lfloor \log_2(n-1)\rfloor$

Summing these two together, one realizes that it is at most $n$.

My comments on the problem:

It is way, way, way too hard for a P1. This should've been put as P4 instead, maybe.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hectorleo123
354 posts
#4
Y by
I would say this is at least a P3 from the CMO.
$\textbf{Solution:}$

Let round \( 0 \) be the initial state (before any updates occur). Define \( G_i \) as the directed graph where the \( n \) players are the vertices, and the directed edges represent the votes after round \( i \), for all \( i \in \{0,1,\dots,n\} \).

$\textbf{Lemma:}$ \( G_i \) contains a unique cycle, and this cycle has length at most \( n - i \). Furthermore, any vertex outside the cycle is part of a directed path of length at most \( n - i \).

$\textbf{Proof:}$ We proceed by induction on \( i \).

$\textbf{Base case:}$ \( i = 0 \) (trivial).

$\textbf{Inductive Hypothesis:}$ Suppose the lemma holds for all \( i < k \leq n \).

$\textbf{Inductive Step:}$ Let \( v_1, v_2, \dots, v_t \) be the vertices of the cycle in \( G_{k-1} \) such that \( v_i \to v_{i+1} \) and \( v_{t+1} = v_1 \), where \( v_1 \) is the first vertex to update its vote in round \( k \).

Observe that we now have \( v_1 \to v_3 \), meaning that \( v_2 \) is no longer part of the cycle in \( G_k \). Notice that the only way a vertex \( v_j \) can leave the cycle and become part of a directed path (i.e., no longer in any cycle) is if there exists a vertex \( w \) in the cycle such that \( w \) votes for \( v_j \) and \( v_j \) previously belonged to the cycle...(\(\alpha\)).

Now, we verify that any directed path outside the cycle has length at most \( n - k \). By the inductive hypothesis, all such paths in \( G_{k-1} \) have length at most \( n - k + 1 \). In each round, the length of every path decreases by at least \( 2 \) from its outermost vertex towards the cycle, while it increases by at most \( 1 \) at the end touching the cycle (by (\(\alpha\))). Therefore, the length of any path is at most \( n - k \).

This completes the induction. Applying the lemma to \( G_n \), we conclude that all \( n \) players will eventually vote for the same person. $_\blacksquare$
This post has been edited 1 time. Last edited by hectorleo123, Mar 8, 2025, 12:38 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
genius_007
275 posts
#5
Y by
I don't think the solution above works fully, from your assumption that the first person to go lies in the cycle. We show how we can make a path grow by more than $2$ every round. Say we have a cycle $C$ and path $P$ coming off of $C$, where $|C| >> |P|$. Let the vertices in $C$ be $v_1,v_2,\dots,v_k$, where $v_i$ points to $v_{i+1}$. WLOG, let the first vertex $w$ of $P$ go to $v_1$. Update $w$ first, so it now points to $v_2$. Update $v_1$, so $v_1$ points to $v_3$. Update $v_2$, so $v_2$ points to $v_4$. Update $v_3$, so $v_3$ points to $v_5$. We may continue this, where $v_i$ points to $v_{i+2}$. In particular, we get the new path $w,v_2,v_4,\dots,v_{2r}$, where $r = \lfloor\dfrac{k}{2}\rfloor$. We've already updated all of those $r+1$ vertices in $P$, so $P$ has new length at least $r$. For large $C$, we are able to increase the length of $P$, which shows your solution is wrong.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hectorleo123
354 posts
#6
Y by
Sorry, my mistake, I meant that after the movement of v_1, v_2 left the cycle, then v_1 could disappear, fixed
This post has been edited 1 time. Last edited by hectorleo123, Mar 12, 2025, 9:55 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cursed_tangent1434
737 posts
#7
Y by
Am I fakesolving or is the problem much easier than the above solutions indicate?

We prove the claim via induction. In the case where $n=2$ the result is trivial. Now, assume the result holds for some positive integer $k \ge 2$. When there are $k+1$ players, consider the very first update. Say this was an update for player $i$. Player $i$ votes for $i+1$ who votes for $i+2 \pmod{k+1}$ so $i$ will now vote for $i+2$. Note that then, there is no player voting for player $i+1$. Since each move replaces the player each player is voting for by some other player who is being voted for by some player, player $i+1$ will never receive a vote from any player ever again.

Now, player $i+1$ can be 'ignored'. He does not have any effect whatsoever on the players everyone else is voting for. However, the player he votes for changes over time (depending on the choices of the other players). Thus, each round can be considered as the conjunction of a round among $k$ players and an extra move for player $i+1$ (which may happen at any time during the round, in the first round it occurred as the first move). After $k$ rounds, players $1$ to $i$ and $i+2$ to $k+1$ will unanimously vote for the same person (who is within this set). Now, if player $i+1$ also votes for this player we are already done. Else, in the last round player $i+1$ adjusts his vote to match someone within the other set of $k$ players who all vote for the same person, which completes the induction.

Thus, repeating the updating procedure for $n$ rounds, always the $n$ players will end up voting for the same person as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
genius_007
275 posts
#8
Y by
This is a fakesolve. After $i$ changes their vote to $i+1$, we cannot directly use the I.H. on $1,2,\dots,i,i+2,\dots,k+1$, as $i$ cannot have their vote updated (they already updated their vote).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lw202277
3 posts
#9 • 2 Y
Y by swynca, MS_asdfgzxcvb
Treat the players and their votes as a directed graph $G$.

Claim: There is exactly 1 cycle $C$ in $G$.

This is initially true. Suppose $a \rightarrow b \rightarrow c$ becomes $a \rightarrow c$ and $b \rightarrow c$. The number of new cycles created is the number of directed paths from $c$ to $a$, and the number of cycles removed is the number of directed paths from $b$ to $a$. Since $b \rightarrow c$, this is equal to the number of directed paths from $c$ to $a$. Therefore the number of cycles stays constant.

Claim: The cycle's size decreases by at least 1 each round. (In hindsight, this was a very weak bound and can be replaced with $O(\log_2 n)$)

Just note that whenever a player $a \in C$ changes their vote from $b$ to $c$, $b$ is removed from the cycle unless $b=c$. If $b=c$ then we must have $a=b=c$ or else there would be no directed path from $b=c$ to $a$. This occurs iff the cycle has size 1.

Claim: Any branch (a directed path pointing into the cycle) has length at most 2, at the end of each round.

Note that any branch with length $\geq 2$ decreases its length when a player not voting for an element of $C$ switches their vote. It suffices to show that no branch can increase its length by more than 1 in any round.

Suppose $a \rightarrow b \rightarrow c$ where $a,b,c \in C$, and let $v_1 \rightarrow \dots \rightarrow v_k \rightarrow b$ be a branch. The only way for the branch to increase its length is for $b$ to be ejected from the cycle, which only occurs when $a$ switches their vote from $b$ to $c$. After this, $c$ is now the endpoint of the branch. Note that $c$ cannot be ejected from the cycle since this would require $a$ to switch their vote from $c$ to another player, which is impossible since $a$ already switched their vote. Thus the branch's length increases by at most 1 each round, which is nullified by it decreasing its length by at least 1 each round.

After round $n-1$ the cycle will have size 1, which is a player voting for themselves. All branches will have length at most 2, and each of these branches will reduce their length to 1 on round $n$. This implies that everyone will be voting for the same player. QED
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ray66
83 posts
#10
Y by
Treat the system as a group where elements consist of players and their respective votes. The group operation turns $a \rightarrow b \rightarrow c$ into $a \rightarrow c$ and $b \rightarrow c$.

$\textbf{Claim: }$ There exists only one cycle in each element

$\textbf{Claim: }$ Each round of operations decreases the length of the cycle by at least 1

$\textbf{Claim: }$ If the length of the cycle is $0$ we finish

$\textbf{Proof: }$ From the starting element (a circular graph) there is only 1 cycle. Each node in a 1-cycle graph can be characterized into nodes that comprise the cycle and nodes that feed into the cycle. The starting element only has nodes that comprise the cycle, and if $a$ and $b$ are both cycle nodes ($a$ and $b$ exist because the cycle length is at least 1), the operation $a \rightarrow b \rightarrow c$ into $a \rightarrow c$ and $b \rightarrow c$ turns $b$ into a feeding node while $a$ and $c$ remain cycle nodes.

$\textbf{Claim: }$ Feeding nodes always point into the cycle

$\textbf{Claim: }$ Each round of operations decrease the length of a feeding chain by at least 1

Because all processes must terminate and there exists exactly 1 cycle in each graph, everyone will eventually vote for the same player.
This post has been edited 1 time. Last edited by ray66, Mar 13, 2025, 3:13 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ru83n05
172 posts
#11
Y by
Here is how to achieve an $O(n)$ bound (which solutions above improve to $\lfloor\log_2 n\rfloor + 1$).

Call a player a leaf if no other player is voting for them. Once a leaf, they will always be a leaf. We claim that after $k\leq n-1$ rounds, there will be at least $k$ leaves.

We prove this by induction. In the first round, the first time a player updates their vote, the person they used to vote for becomes a leaf. Hence this is true when $k=1$.

Now, suppose we know the statement is true for $k$. If there exists a player that is only voted by leafs, that player will become a leaf at the end of the round. Otherwise, all non-leaf players are being voted by at least one non-leaf, and therefore exactly one non-leaf. In that case, the first time a non-leaf (in a nontrivial cycle) updates their vote, we get a vertex that is only voted by leafs. Hence by the end of the round we always get an extra leaf.

In particular, after $n-1$ rounds, all players will be voting for the same person.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
heheman
1090 posts
#13
Y by
how are u guys so genius bro teach me how i cant solve the first problem im gonna rage
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
genius_007
275 posts
#14 • 1 Y
Y by heheman
tbf this was arguably the hardest question on CMO this year, a lot of people were not able to solve
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
heheman
1090 posts
#15
Y by
guys, i think i got it!!!!

First draw graph with vertices representing players, and if $a$ votes for $b$ then there's arrow directed from $a$ to $b$. call the graph "connected" if the graph is connected when viewing the directed edges as undirected.

Observation 1: graph is always connected
Proof: note that every operation preserves it

Thus there is only ever 1 cycle in the whole graph, since if there is $2$ the only way it can exist if they are disjoint. not true by our observation.

Now note that the cycle decreases by at least $1$ for every turn. Note that during any turn it will always preserve the cycle structure. and at the end there are 2 arrows pointing to the same vertex by pigeonhole so one of them must have no arrow pointing to so it loses at least 1. note

anyways, let $k$ be the largest distance from a point traveling from outside the cycle needs to enter the cycle. Note that $k$ goes to $k-1+[$# of pts removed from the cycle}$]$ after every turn (or simply $k+[$# of pts removed from the cycle$]$ if $k$ was $0$ which is only at first turn, or $1$), at the worst case.

But every time some x = [# pts is removed from the cycle] is removed, it buys us $x-1$ turns of extra time in the future so we can subtract all of it from $k$

class ended so i am need to be brief
This post has been edited 1 time. Last edited by heheman, Jun 10, 2025, 10:47 PM
Reason: indexing error(was $0$ which is only at first turn -> was $0$ which is only at first turn, or $1$.)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1780 posts
#16 • 1 Y
Y by heheman
I think most people who tried to do arguments of the form "cycle decreases by at least 1 each turn" got a 2/7

lol
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
heheman
1090 posts
#17
Y by
awesomeming327. wrote:
I think most people who tried to do arguments of the form "cycle decreases by at least 1 each turn" got a 2/7

lol

o sadge

do u know wut errors they might've made, idk if i fakesolve
Z K Y
N Quick Reply
G
H
=
a