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
May 1, 2025
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
May 1, 2025
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
Functional inequality condition
WakeUp   3
N a minute ago by AshAuktober
Source: Italy TST 1995
A function $f:\mathbb{R}\rightarrow\mathbb{R}$ satisfies the conditions
\[\begin{cases}f(x+24)\le f(x)+24\\ f(x+77)\ge f(x)+77\end{cases}\quad\text{for all}\ x\in\mathbb{R}\]
Prove that $f(x+1)=f(x)+1$ for all real $x$.
3 replies
WakeUp
Nov 22, 2010
AshAuktober
a minute ago
Asymmetric FE
sman96   16
N 2 minutes ago by jasperE3
Source: BdMO 2025 Higher Secondary P8
Find all functions $f: \mathbb{R} \to \mathbb{R}$ such that$$f(xf(y)-y) + f(xy-x) + f(x+y) = 2xy$$for all $x, y \in \mathbb{R}$.
16 replies
sman96
Feb 8, 2025
jasperE3
2 minutes ago
Existence of a rational arithmetic sequence
brianchung11   28
N 11 minutes ago by cursed_tangent1434
Source: APMO 2009 Q.4
Prove that for any positive integer $ k$, there exists an arithmetic sequence $ \frac{a_1}{b_1}, \frac{a_2}{b_2}, \frac{a_3}{b_3}, ... ,\frac{a_k}{b_k}$ of rational numbers, where $ a_i, b_i$ are relatively prime positive integers for each $ i = 1,2,...,k$ such that the positive integers $ a_1, b_1, a_2, b_2, ...,  a_k, b_k$ are all distinct.
28 replies
brianchung11
Mar 13, 2009
cursed_tangent1434
11 minutes ago
NT from EGMO 2018
BarishNamazov   39
N 18 minutes ago by cursed_tangent1434
Source: EGMO 2018 P2
Consider the set
\[A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.\]
[list=a]
[*]Prove that every integer $x \geq 2$ can be written as the product of one or more elements of $A$, which are not necessarily different.

[*]For every integer $x \geq 2$ let $f(x)$ denote the minimum integer such that $x$ can be written as the
product of $f(x)$ elements of $A$, which are not necessarily different.
Prove that there exist infinitely many pairs $(x,y)$ of integers with $x\geq 2$, $y \geq 2$, and \[f(xy)<f(x)+f(y).\](Pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if $x_1 \neq x_2$ or $y_1 \neq y_2$).
[/list]
39 replies
BarishNamazov
Apr 11, 2018
cursed_tangent1434
18 minutes ago
ISI UGB 2025 P6
SomeonecoolLovesMaths   2
N 19 minutes ago by Mathgloggers
Source: ISI UGB 2025 P6
Let $\mathbb{N}$ denote the set of natural numbers, and let $\left( a_i, b_i \right)$, $1 \leq i \leq 9$, be nine distinct tuples in $\mathbb{N} \times \mathbb{N}$. Show that there are three distinct elements in the set $\{ 2^{a_i} 3^{b_i} \colon 1 \leq i \leq 9 \}$ whose product is a perfect cube.
2 replies
SomeonecoolLovesMaths
5 hours ago
Mathgloggers
19 minutes ago
ISI UGB 2025 P2
SomeonecoolLovesMaths   2
N 23 minutes ago by SomeonecoolLovesMaths
Source: ISI UGB 2025 P2
If the interior angles of a triangle $ABC$ satisfy the equality, $$\sin ^2 A + \sin ^2 B + \sin^2  C = 2 \left( \cos ^2 A + \cos ^2 B + \cos ^2 C \right),$$prove that the triangle must have a right angle.
2 replies
SomeonecoolLovesMaths
5 hours ago
SomeonecoolLovesMaths
23 minutes ago
angle chasing in RMO, cyclic ABCD, 2 circumcircles, incenter, right wanted
parmenides51   5
N 26 minutes ago by Krishijivi
Source: CRMO 2015 region 1 p1
In a cyclic quadrilateral $ABCD$, let the diagonals $AC$ and $BD$ intersect at $X$. Let the circumcircles of triangles $AXD$ and $BXC$ intersect again at $Y$ . If $X$ is the incentre of triangle $ABY$ , show that $\angle CAD = 90^o$.
5 replies
parmenides51
Sep 30, 2018
Krishijivi
26 minutes ago
Short combi omg
Davdav1232   6
N 27 minutes ago by DeathIsAwe
Source: Israel TST 2025 test 4 p3
Let \( n \) be a positive integer. A graph on \( 2n - 1 \) vertices is given such that the size of the largest clique in the graph is \( n \). Prove that there exists a vertex that is present in every clique of size \( n\)
6 replies
Davdav1232
Feb 3, 2025
DeathIsAwe
27 minutes ago
Lots of midpoints
Jackson0423   0
33 minutes ago

In triangle \( ABC \), suppose \( AB = BC \). Let \( M \) be the midpoint of \( AB \), and let \( K \) be a point inside the triangle such that \( AM = AK \) and \( CK = CB \).
If \( AC=y \), Find \( \sin \angle AKC \).
0 replies
Jackson0423
33 minutes ago
0 replies
Some combinatorics
giangtruong13   0
an hour ago
Let $A$ be a set of $n$ point ($n $ is integer number, $n \geq 4$). On a plane take 3 points randomly which can form a triangle that has the area $ >1$. Prove that: All points in set $A$ lie inside a triangle that has the area $\leq 4$
0 replies
giangtruong13
an hour ago
0 replies
Interesting inequalities
sqing   0
an hour ago
Source: Own
Let $ a,b,c\geq 0 , (2a+3)(b+4c)=5.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq \frac{27}{20}$$Let $ a,b,c\geq 0 , (4a+5)(b+6c)=7.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq \frac{17}{12}$$Let $ a,b,c\geq 0 , (a+2)(b+3c)=4.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq \frac{2+\sqrt 3}{4}$$Let $ a,b,c\geq 0 , (a+3)(b+6c)=9.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq \frac{7+2\sqrt 6}{16}$$Let $ a,b,c\geq 0 , (a+4)(b+8c)= 16.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{9+4\sqrt 2}{25}$$Let $ a,b,c\geq 0 , (a+2)(b+5c)=2.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq \frac{3+\sqrt 5}{4}$$Let $ a,b,c\geq 0 , (3a+2)(b+5c)= 5.$ Prove that
$$a+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{4(3+\sqrt 5)}{17}$$
0 replies
sqing
an hour ago
0 replies
Interesting inequalities
sqing   5
N an hour ago by sqing
Source: Own
Let $ a,b,c\geq 0 , (a+k )(b+c)=k+1.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{2k-3+2\sqrt{k+1}}{3k-1}$$Where $ k\geq \frac{2}{3}.$
Let $ a,b,c\geq 0 , (a+1)(b+c)=2.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq 2\sqrt{2}-1$$Let $ a,b,c\geq 0 , (a+3)(b+c)=4.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{7}{4}$$Let $ a,b,c\geq 0 , (3a+2)(b+c)= 5.$ Prove that
$$\frac{1}{a+1}+\frac{1}{b+1}+\frac{1}{c+1}\geq  \frac{2(2\sqrt{15}-5)}{3}$$
5 replies
sqing
Yesterday at 1:29 PM
sqing
an hour ago
ISI UGB 2025 P4
SomeonecoolLovesMaths   3
N an hour ago by SomeonecoolLovesMaths
Source: ISI UGB 2025 P4
Let $S^1 = \{ z \in \mathbb{C} \mid |z| =1 \}$ be the unit circle in the complex plane. Let $f \colon S^1 \longrightarrow S^2$ be the map given by $f(z) = z^2$. We define $f^{(1)} \colon = f$ and $f^{(k+1)} \colon = f \circ f^{(k)}$ for $k \geq 1$. The smallest positive integer $n$ such that $f^{(n)}(z) = z$ is called the period of $z$. Determine the total number of points in $S^1$ of period $2025$.
(Hint : $2025 = 3^4 \times 5^2$)
3 replies
SomeonecoolLovesMaths
5 hours ago
SomeonecoolLovesMaths
an hour ago
ISI UGB 2025 P7
SomeonecoolLovesMaths   7
N an hour ago by SomeonecoolLovesMaths
Source: ISI UGB 2025 P7
Consider a ball that moves inside an acute-angled triangle along a straight line, unit it hits the boundary, which is when it changes direction according to the mirror law, just like a ray of light (angle of incidence = angle of reflection). Prove that there exists a triangular periodic path for the ball, as pictured below.

IMAGE
7 replies
SomeonecoolLovesMaths
5 hours ago
SomeonecoolLovesMaths
an hour ago
Y2K Game
MithsApprentice   13
N Apr 11, 2025 by zuat.e
Source: USAMO 1999 Problem 5
The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.
13 replies
MithsApprentice
Oct 3, 2005
zuat.e
Apr 11, 2025
Y2K Game
G H J
Source: USAMO 1999 Problem 5
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MithsApprentice
2390 posts
#1 • 3 Y
Y by Adventure10, Mango247, Supercali
The Y2K Game is played on a $1 \times 2000$ grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins. If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathjoker
258 posts
#2 • 2 Y
Y by Adventure10, Mango247
This was the last USAMO that I took as a high school student. I remember being very frustrated with this problem - I wasn't very well-educated about inequalities, so I was able to do #4 only after a couple of hours of effort. That would have left only an hour or so for this problem. Also, I think I misinterpreted the problem as saying that the first player is only allowed to write the letter S and the second player can only write the letter O.

I recently worked on this problem some more (ahh, nostalgia!), this time using the correct interpretation of the problem. Here is the solution I came up with. I don't know if the out-of-high-school-for-well-nigh-a-decade crowd is allowed to post here. If not, feel free to remove this post. But I felt a deep sense of joy when I found this solution and I hope I can share that with the interested reader.

[redacted - I will repost this tomorrow]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tim1234133
523 posts
#3 • 2 Y
Y by Adventure10, Mango247
Let's call the first player A, the second player B.

B's strategy is as follows:
On his first turn, place an S in a square far away from both ends of the board and A's first counter.
On his second turn (unless he can finish an SOS somewhere), place an S three squares to one side of his first S, and if A has put his second counter 'near' B's first, make sure it is on the other side from this one.

After this, B follows the following algorithm:

If he can finish an SOS somewhere, do so.
Otherwise, if there is an empty square with a square each side empty, put an O in it.
Otherwise, where there is an empty square with neither adjacent square empty, put an O in it.

[Whenever B plays, there are an odd number of empty squares, so at least one of the above is always possible].

If I have got it right, it should be fairly apparent that A cannot win with B following this. To ensure that B actually wins-
At the beginning, B created a sequence of four squares that went S-empty-empty-S. At some point, A must place an O or S in one of these squares: then B just has to put the other one in the other empty square and he wins.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CHrs
1 post
#4 • 2 Y
Y by Adventure10, Mango247
Is there also a winning stategy for the first player, player A?
gr, C
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
#5 • 2 Y
Y by Adventure10, Mango247
By the definition of winning strategy (a strategy that one player can follow such that she can win regardless of the actions of all other players), the number of players who can have winning strategies is at most the number of possible simultaneous winners. Since at most one player wins this game, at most one player can have a winning strategy.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CatalystOfNostalgia
1479 posts
#6 • 4 Y
Y by Adventure10, Mango247, panche, and 1 other user
The second player wins. The strategy is to place an S on his first turn far enough away from the ends of the board and the first player's first move, and play an S three boxes down on the next move. Note that if anyone is ever forced to play in one in a pair of boxes between two S's (S/_/_/S), let this be a domino of death, the other player will automatically win on the next turn, and furthermore it is impossible that the original player can win.

We will prove that the only way for anybody to play such that the other player wins on the next turn is if he is forced to play in a domino of death. We claim that if there is an empty box that is not in a domino of death, the person whose turn it is can either (a) win or (b) play in such an empty box such that the other player can't win on the next turn.

If the player P has the chance to win, then he can just win. Thus, if he can't win and furthermore has to play such that the other player Q wins on the next turn, the Q's SOS must include the letter that the P played. We have 3!=6 cases. For example,

P plays the first S, Q plays the O. We seek all situations such that if P played O instead, Q still could have won. Basically, the board is going to look like _/_/S before P plays, and O/_/S in the alternative strategy. If this still allows Q to win, then it must be because there's an S in the middle and an S to the left of an O; we have a domino of death.

The other five cases work the same way, we find that we need Q to have played in a domino of death. Note that the second player in our game can always avoid playing in a domino of death because he always plays with an odd number of boxes available (as 2000 is even), and dominoes of death contain two boxes each, with one box only being a member of at most one domino of death. Thus, there's at least one un-paired empty box and thus at least one box not part of a domino of death for the second player to play in.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MSTang
6012 posts
#7 • 8 Y
Y by math114, rkm0959, anantmudgal09, vsathiam, Delray, UK2019Project, Adventure10, Mango247
Nothing new here, but I love this problem :)

Solution
This post has been edited 2 times. Last edited by MSTang, Aug 18, 2015, 2:41 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yayups
1614 posts
#8 • 3 Y
Y by Casetoo, Adventure10, Mango247
View the board position as a string of the characters S,O,-. Call the players Alice and Bob.

We prove a series of lemmas to prove that Bob will win if both players play optimally.

Lemma 1: Bob can make sure that there is some turn of his where the board has a substring S--S.

Proof of Lemma 1: If Alice opens with placing an S somewhere, then Bob simply places another S to get the substring S--S somewhere. We're not done yet since it is now Alice's turn. But if she plays in one of the two blanks in the S--S, it is easy to see that Bob wins, so Alice must play outside the --. Therefore, it is Bob's turn, and the substring S--S exists.

Now, assume she instead opens with playing an O somewhere. Bob should then place an S far from the O and the edges of the board (fifty squares from the O and the edges should suffice). Alice won't play so that Bob can complete an SOS, since she is playing optimally, so she plays something else. Now, on Bob's second move, he has two ways to make the S--S, but at most one of them could lead to a winning position for Alice because of her second move. So he just plays the one that won't lead to a winning position for Alice, so Alice's third turn is not a win, so Bob's third turn arrives with the substring S--S existing somewhere on the board. $\blacksquare$

An important consequence of this lemma is that the game will now not draw - eventually someone must play in the blanks in S--S, and then they lose.

Lemma 2: Once Bob has S--S somewhere, Bob can have the ends of the board to be filled on one of his turns.

Proof of Lemma 2: Suppose Bob has S--S and it is his turn, and WLOG Bob can't immedeatly win (else game over). If an edge square is empty, by putting an O on the edge, Bob adds no winning positions, so Alice makes a move that doesn't finish, so its Bob's turn again. Thus, Bob can fill up the edges. $\blacksquare$

Lemma 3: If Bob can't win on a turn, then he can play so that he will be around to play another turn.

Proof of Lemma 3: Suppose there is a substring of the form -O or O-. Certainly if Bob adds an O to make them OO, then he could not have added any new winning substring (a winning substring is SO-, S-S, or -OS). Thus, WLOG assume that there are no substrings of the form -O or O-.

Thus, the board looks like
\[X_1(-)^{a_1}X_2(-)^{a_2}\cdots (-)^{a_n}X_{n+1}\]where $X_i$ is a string of S and Os that starts and ends with S (except maybe $X_1$ and $X_{n+1}$ that could start and end with O respectively), and has no substring of the form SOS, and $a_i\ge 2$ for all $i$. If any of the $a_i\ge 3$, then Bob should simply put an S in the first - in $(-)^{a_i}$. It is easy to see that this adds no winning substrings, so it suffices to examine the case $a_1=\cdots=a_n=2$. But this means that the number of squares placed so far is $2000-2n$, which is even, so it can't even be Bob's turn! Therefore, we are done. $\blacksquare$

Lemma 1 implies that there is no draw, and lemma 3 implies that Bob won't lose, so Bob must win.

QED
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Contradiction
62 posts
#9 • 1 Y
Y by Adventure10
If we generalize $2000$ to $n$, the first player wins for all odd $n(\geq7)$ and the second player wins for all even $n(\geq14)$
The rest becomes a tie, checking the remaining cases.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ZETA_in_olympiad
2211 posts
#10
Y by
My second combinatorics solution here :D

Let the players be X and Y. In Y's first move, place an S far from the boards corners and X's move. Remember, whenever SOS possible, do it. In second move create a S[][]S next to the first move, in case X played something near the first move, play the second S in the opposite side. Now do either: 1) If x[]x (x=S or O) then put O. 2) If [][][] then put O in middle. This is possible because there are odd squares after X plays. Continuing like this X must once put a S or O in the S[][]S, then Y wins.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
signifance
140 posts
#11
Y by
OH YEAHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH I GET IT NOW NOOOOOWWWWWWWW IT MAKES SENSSEEEEEEEEEEEEEEEEE

whatever A plays, B plays >3 squares away from all sides and >5 squares away from A a letter S. Obviously if A threatens to win then B wins, so henceforth assume A is never one move from winning when it's B's turn. Next move B can guarantee to place another S three spots away from the first S. Now he can just fill up the rest of the board accordingly by spamming Os wherever there are three empty spots (he places it in the middle), or wherever both spots are occupied. Note that if he runs out of moves in this algorithm, he can just place an O next to another O, and if he runs out of these moves, the config is made up of some blocks of [block]xx[block=SOO...OOS]... etc., so everything is filled except for some areas of SxxS. However, in each one of these, there are an even number of unfilled, so actually, it must be 1's move. Now wherever 1 moves in one of these blocks player 2 just moves the opposite type in the other x, and wins.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
InterLoop
280 posts
#12
Y by
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8863 posts
#13
Y by
Call a nuke a set of two squares filled with $S$ that have exactly two squares between them. We call a square exposed if there exists a neighbor of that square which is not yet filled.

Claim: The second player can always construct a nuke.

Proof: No matter what the first player plays on his turn, the second player can pick an empty square and fill it with $S$, such that the two squares a distance of $3$ from that square are both unoccupied. On the first player's next turn, he can only fill one of those squares, so the second player can fill the other square, hence building a nuke. $\blacksquare$

Now the second player plays detente and just makes sure he doesn't die. In particular, he adopts the following strategy:
  • If there exists an exposed $O$ square, he fills a square adjacent to it with $O$;
  • If there exists an exposed $S$ square that is not part of a nuke, he fills a square adjacent to it with $S$.
Claim: The second player can always make such a move or win on his turn.

Proof: If he cannot make a move, this means that all remaining exposed $S$ squares are part of nukes, and no $O$ is exposed. In particular, adjacent unfilled squares must come in groups of $1$ or $2$. But if there exists an isolated unfilled square, it must be surrounded by two $S$ squares, so the second player can win by playing $O$ in the middle. If all adjacent unfilled squares come in groups of $2$, then there are an even number of unfilled squares remaining, so it can't be the second player's turn! $\blacksquare$

Claim: The second player never enters a losing position by playing either move.

Proof: This is easy to check: the second player never creates an adjacent pair of $O$ and $S$ squaers or two $S$ squares with one square in between. If such a pair existed on his turn, he can win immediately; thus he never enters a losing position. $\blacksquare$

It follows that when the second player can no longer make one of the two moves, the first player will get nuked on his next turn because there is at least one nuke. GG.

Remark: I apologize for the existential flavortext; I was inspired by the problem statement.
This post has been edited 1 time. Last edited by HamstPan38825, Jan 6, 2025, 6:29 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
zuat.e
56 posts
#14
Y by
Say that a position is a winning position for a player if he can directly win just by writing one letter.

We claim the following:
Claim: If the first player wins, then the second player had a winning position the previous turn
Proof: For the first player to win regardless of the last move of the second one, consider the square $-$ the second player wrote on:
(i) Writing an $O$ would mean losing, hence we need $S-$ (or $-S$ but we assume $S-$ WLOG)
(ii) Writing an $S$ would also mean losing, implying $-xS$, where $x$ is the letter of the square to the right of our considered square

Combining both cases yields $S-xS$, but placing any letter both in our considered square or on the square to its right loses automatically, so both must have been empty beforehand.
As $S-xS$ is the only possibility for the second player to lose, we must only have that configuration repeated a number of times and every other square must have something written on (if not the second player writes on that other square), however this implies that the number of empty squares is odd, resulting on being on the first player's turn.


Consequently, in his first turn, the second player will write an $S$ separated enough from the first player's first letter, then the first player will write another letter $l$: if it becomes a winning position for the second player, he wins and otherwise he finishes the $S--S$ (where $-$ are squares), which is guaranteed because he chooses the second $S$ to be at the opposite side of $l$ $w.r.t$ the first $S$ and clearly the first player doesn't have a winning position and so the second player can play carefully to not give winning positions to the first player and the first player will eventually have to write in some $S--S$ (maybe not the first we have created but one created by further play) and the second player will have a winning position.
Z K Y
N Quick Reply
G
H
=
a