We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/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, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
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
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
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, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
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
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
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
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
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
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
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

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
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
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
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
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
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
Friday, Apr 11 - Jun 27
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
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
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

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
Monday, Mar 24 - Jun 16
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
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 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
Wait wasn't it the reciprocal in the paper?
Supercali   6
N 27 minutes ago by kes0716
Source: India TST 2023 Day 2 P1
Let $\mathbb{Z}_{\ge 0}$ be the set of non-negative integers and $\mathbb{R}^+$ be the set of positive real numbers. Let $f: \mathbb{Z}_{\ge 0}^2 \rightarrow \mathbb{R}^+$ be a function such that $f(0, k) = 2^k$ and $f(k, 0) = 1$ for all integers $k \ge 0$, and $$f(m, n) = \frac{2f(m-1, n) \cdot f(m, n-1)}{f(m-1, n)+f(m, n-1)}$$for all integers $m, n \ge 1$. Prove that $f(99, 99)<1.99$.

Proposed by Navilarekallu Tejaswi
6 replies
+1 w
Supercali
Jul 9, 2023
kes0716
27 minutes ago
Inspired by Kazakhstan 2017
sqing   0
38 minutes ago
Source: Own
Let $a,b,c\ge \frac{1}{2}$ and $a+b+c=2. $ Prove that
$$\left(\frac{1}{a}+\frac{1}{b}-\frac{1}{c}\right)\left(\frac{1}{a}-\frac{1}{b}+\frac{1}{c}\right)\ge 1$$Let $a,b,c\ge \frac{1}{3}$ and $a+b+c=1. $ Prove that
$$\left(\frac{1}{a}+\frac{1}{b}-\frac{1}{c}\right)\left(\frac{1}{a}-\frac{1}{b}+\frac{1}{c}\right)\ge 9$$
0 replies
1 viewing
sqing
38 minutes ago
0 replies
About old Inequality
perfect_square   0
44 minutes ago
Source: Arqady
This is: $a,b,c>0$ which satisfy $abc=1$
Prove that: $ \frac{a+b+c}{3} \ge \sqrt[10]{\frac{a^3+b^3+c^3}{3}}$
By $  uvw $ method, I can assum $b=c=x,a=\frac{1}{x^2}$
But I can't prove:
$ \frac{2x+\frac{1}{x^2}}{3} \ge \sqrt[10]{ \frac{2x^3+ \frac{1}{x^6}}{3}} $
Is there an another way?
0 replies
perfect_square
44 minutes ago
0 replies
inquality
karasuno   1
N an hour ago by sqing
The real numbers $x,y,z \ge \frac{1}{2}$ are given such that $x^{2}+y^{2}+z^{2}=1$. Prove the inequality $$(\frac{1}{x}+\frac{1}{y}-\frac{1}{z})(\frac{1}{x}-\frac{1}{y}+\frac{1}{z})\ge 2 .$$
1 reply
karasuno
2 hours ago
sqing
an hour ago
Number Theory
karasuno   0
2 hours ago
Solve the equation $$n!+10^{2014}=m^{4}$$in natural numbers m and n.
0 replies
karasuno
2 hours ago
0 replies
Minimum number of values in the union of sets
bnumbertheory   5
N 2 hours ago by Rohit-2006
Source: Simon Marais Mathematics Competition 2023 Paper A Problem 3
For each positive integer $n$, let $f(n)$ denote the smallest possible value of $$|A_1 \cup A_2 \cup \dots \cup A_n|$$where $A_1, A_2, A_3 \dots A_n$ are sets such that $A_i \not\subseteq A_j$ and $|A_i| \neq |A_j|$ whenever $i \neq j$. Determine $f(n)$ for each positive integer $n$.
5 replies
bnumbertheory
Oct 14, 2023
Rohit-2006
2 hours ago
two triangles have equal circumradii
littletush   5
N 3 hours ago by Taha.kh
Source: Italy TST 2009 p5
Two circles $O_1$ and $O_2$ intersect at $M,N$. The common tangent line nearer to $M$ of the two circles touches $O_1,O_2$ at $A,B$ respectively. Let $C,D$ be the symmetric points of $A,B$ with respect to $M$ respectively. The circumcircle of triangle $DCM$ intersects circles $O_1$ and $O_2$ at points $E,F$ respectively which are distinct from $M$. Prove that the circumradii of the triangles $MEF$ and $NEF$ are equal.
5 replies
littletush
Mar 10, 2012
Taha.kh
3 hours ago
Equal lengths in cyclic quadrilateral
LoloChen   4
N 3 hours ago by Nari_Tom
Source: All-Russian MO 2024 9.4
In cyclic quadrilateral $ABCD$, $\angle A+ \angle D=\frac{\pi}{2}$. $AC$ intersects $BD$ at ${E}$. A line ${l}$ cuts segment $AB, CD, AE, DE$ at $X, Y, Z, T$ respectively. If $AZ=CE$ and $BE=DT$, prove that the diameter of the circumcircle of $\triangle EZT$ equals $XY$.
4 replies
LoloChen
Apr 22, 2024
Nari_Tom
3 hours ago
Two circles and many points
CHN_Lucas   5
N 4 hours ago by Captainscrubz
Source: 2022 China Second Round A2
$A,B,C,D,E$ are points on a circle $\omega$, satisfying $AB=BD$, $BC=CE$. $AC$ meets $BE$ at $P$. $Q$ is on $DE$ such that $BE//AQ$. Suppose $\odot(APQ)$ intersects $\omega$ again at $T$. $A'$ is the reflection of $A$ wrt $BC$. Prove that $A'BPT$ lies on the same circle.
5 replies
CHN_Lucas
Dec 22, 2022
Captainscrubz
4 hours ago
Angle QRP = 90°
orl   12
N 4 hours ago by YaoAOPS
Source: IMO ShortList, Netherlands 1, IMO 1975, Day 1, Problem 3
In the plane of a triangle $ABC,$ in its exterior$,$ we draw the triangles $ABR, BCP, CAQ$ so that $\angle PBC = \angle CAQ = 45^{\circ}$, $\angle BCP = \angle QCA = 30^{\circ}$, $\angle ABR = \angle RAB = 15^{\circ}$.

Prove that

a.) $\angle QRP = 90\,^{\circ},$ and

b.) $QR = RP.$
12 replies
orl
Nov 12, 2005
YaoAOPS
4 hours ago
IMO 2014 Problem 4
ipaper   166
N 4 hours ago by hgomamogh
Let $P$ and $Q$ be on segment $BC$ of an acute triangle $ABC$ such that $\angle PAB=\angle BCA$ and $\angle CAQ=\angle ABC$. Let $M$ and $N$ be the points on $AP$ and $AQ$, respectively, such that $P$ is the midpoint of $AM$ and $Q$ is the midpoint of $AN$. Prove that the intersection of $BM$ and $CN$ is on the circumference of triangle $ABC$.

Proposed by Giorgi Arabidze, Georgia.
166 replies
ipaper
Jul 9, 2014
hgomamogh
4 hours ago
IMO 2016 Problem 1
quangminhltv99   146
N 4 hours ago by Ilikeminecraft
Source: IMO 2016
Triangle $BCF$ has a right angle at $B$. Let $A$ be the point on line $CF$ such that $FA=FB$ and $F$ lies between $A$ and $C$. Point $D$ is chosen so that $DA=DC$ and $AC$ is the bisector of $\angle{DAB}$. Point $E$ is chosen so that $EA=ED$ and $AD$ is the bisector of $\angle{EAC}$. Let $M$ be the midpoint of $CF$. Let $X$ be the point such that $AMXE$ is a parallelogram. Prove that $BD,FX$ and $ME$ are concurrent.
146 replies
quangminhltv99
Jul 11, 2016
Ilikeminecraft
4 hours ago
A function equation
YaWNeeT   8
N 5 hours ago by HamstPan38825
Source: 2017 Taiwan TST 2nd round day 2 P4
Find all integer $c\in\{0,1,...,2016\}$ such that the number of $f:\mathbb{Z}\rightarrow\{0,1,...,2016\}$ which satisfy the following condition is minimal:
(1) $f$ has periodic $2017$
(2) $f(f(x)+f(y)+1)-f(f(x)+f(y))\equiv c\pmod{2017}$

Proposed by William Chao
8 replies
YaWNeeT
Apr 15, 2017
HamstPan38825
5 hours ago
Circumcenter lies on altitude
ABCDE   58
N 5 hours ago by cj13609517288
Source: 2016 ELMO Problem 2
Oscar is drawing diagrams with trash can lids and sticks. He draws a triangle $ABC$ and a point $D$ such that $DB$ and $DC$ are tangent to the circumcircle of $ABC$. Let $B'$ be the reflection of $B$ over $AC$ and $C'$ be the reflection of $C$ over $AB$. If $O$ is the circumcenter of $DB'C'$, help Oscar prove that $AO$ is perpendicular to $BC$.

James Lin
58 replies
ABCDE
Jun 24, 2016
cj13609517288
5 hours ago
Infinite process on a board
Tsukuyomi   23
N Oct 21, 2024 by DottedCaculator
Source: IMO Shortlist 2018 C6
Let $a$ and $b$ be distinct positive integers. The following infinite process takes place on an initially empty board.

[list=i]
[*] If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by $a$ and the other by $b$.
[*] If no such pair exists, we write two times the number $0$.
[/list]
Prove that, no matter how we make the choices in $(i)$, operation $(ii)$ will be performed only finitely many times.

Proposed by Serbia.
23 replies
Tsukuyomi
Jul 17, 2019
DottedCaculator
Oct 21, 2024
Infinite process on a board
G H J
G H BBookmark kLocked kLocked NReply
Source: IMO Shortlist 2018 C6
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Tsukuyomi
31 posts
#1 • 2 Y
Y by megarnie, Adventure10
Let $a$ and $b$ be distinct positive integers. The following infinite process takes place on an initially empty board.
  1. If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by $a$ and the other by $b$.
  2. If no such pair exists, we write two times the number $0$.
Prove that, no matter how we make the choices in $(i)$, operation $(ii)$ will be performed only finitely many times.

Proposed by Serbia.
This post has been edited 4 times. Last edited by Tsukuyomi, Jul 17, 2019, 12:56 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sepled
10 posts
#2 • 4 Y
Y by NaPrai, MilosMilicevonAoPS, guptaamitu1, Adventure10
The official solution is really great. (See the IMO official!) But this one is the sketch of the solution I submitted during the test. (I will not go in the detail as it is super messy.)

solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#3 • 5 Y
Y by v4913, Pascal96, megarnie, Adventure10, Mango247
Similar problem on China TST 2018.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
distortedwalrus
193 posts
#4 • 1 Y
Y by Adventure10
This is my idea (I hope it is correct).

sketch
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rzlng
99 posts
#5 • 9 Y
Y by SpecialBeing2017, MathAwesome123, sriraamster, Contradiction, rashah76, zschess, Adventure10, Mango247, sabkx
This solution, due to MathAwesome123 is different from the previous ones: It uses a brilliant algebraic invariant argument inspired by the classic escape of the clones / Conway's Checkers. :)

Edit: this solution doesn't work - see goldenboy's comment below

solution

https://artofproblemsolving.com/community/c996208h1950519_isl_2018_c6
This post has been edited 5 times. Last edited by rzlng, Jul 4, 2020, 7:34 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
PedroBigMan
14 posts
#6 • 1 Y
Y by Adventure10
This problem can be solved very easily using Chip Firing Lemma on an infinite directed graph. Notice that the problem is just proving that the CFG with initial setting of chips being k chips on node 0 and 0 chips on all other nodes is finite for sufficiently large k.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GoldenBoy03
22 posts
#7 • 1 Y
Y by CBMaster
rzlng wrote:
This solution, due to MathAwesome123 is different from the previous ones: It uses a brilliant algebraic invariant argument inspired by the classic escape of the clones / Conway's Checkers. :)

solution

https://artofproblemsolving.com/community/c996208h1950519_isl_2018_c6

What if y=a-1?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jclash
92 posts
#8
Y by
rzlng wrote:
Let $\mathcal{B}$ be the multiset of integers currently written on the board. Define the quantity\[S=\sum_{n\in\mathcal{B}}f(n). \]We claim that $S$ is preserved under type (i) operations. It suffices to show that $2f(n)=f(n+a)+f(n+b)$, which is $2\cdot \varphi^{2y-x}=\varphi^{2y+2-x}+\varphi^{2y-x-1}$, or $2\varphi=\varphi^2+\varphi^{-1}$. This follows from the fact that $\varphi^2=\varphi+1$ and $\varphi^{-1}=\varphi-1$ (by rearrangements of $\varphi^2-\varphi-1=0$).

Correct me if I'm wrong, I might just be really bad at algebra, but isn't this false?
\[2f(n) = 2\varphi^{2y-x}\]\[f(n+a)+f(n+b) = \varphi^{2y-x+2} + \varphi^{2y-x-1} = \varphi^{2y-x}(\varphi^2 + \varphi^{-1}) = 2\varphi^{2y-x+1}\]and these two are not equal? I had a similar idea of firing points, with $2 \cdot (x, y) \Rightarrow (x+1, y) \cup (x, y+1)$ where $(x, y)$ denotes $xa+yb$ but the only invariant I really bothered to find was $x-y$. However I believed this is solved denoting $2f(n = xa + yb) = 2\varphi^{x-2y} = \varphi^{x-2y}((1 - \frac{1}{\varphi}) + (1 + \frac{1}{\varphi})) = \varphi^{x-2y}(\frac{1}{\varphi^2} + \varphi) = \varphi^{x-2y+1} + \varphi^{x-2y-2} = f((x+1)a + yb) + f(xa + (y+1)b) = f(n+a) + f(n+b)$
This post has been edited 5 times. Last edited by jclash, Jun 3, 2020, 8:10 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jclash
92 posts
#9
Y by
Sepled wrote:
Proof In fact, $$\{0,0,a,2a,...,(b-1)a,b,2b,...,(a-1)b\}$$satisfy the Claim. The proof is bashing everything out. (The actual proof is too messy and I'm too lazy to show that.)

While this works it is not achievable in a "real game" right. If you just choose $a$ to be a super small prime like $17$ and $b$ to be some huge prime in the millions then it's obvious that achievement of this configuration is impossible. Not to mention you're trying not to perform operation i, so you can always choose pairs so it never gets here and you're forced into ii
This post has been edited 1 time. Last edited by jclash, Jun 3, 2020, 8:20 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sepled
10 posts
#10 • 1 Y
Y by Mango247
@above. Since I already proved that the order of operation (even mixing up between i and ii) does not affect the ending result. I just need to prove that each number is reachable from the starting point. This is pretty obvious because we could make all numbers in the form $ax+by$ when $x,y \geq 0.$ There is no reason to care whether it could be achieved by the condition that enforces the second rule on using operation. We could swap in any way we want.

Forget to mention that WLOG $gcd(a,b)=1)$

Also, this number is achievable even though the second rule still applies. Here's the trick. You could prove that for $f(n,k)$ that is the function which counts the number of times $n$ appear after applying operation 2 for $k$ times. Then, $f(xa,k) \equiv 1 \pmod{2}$ for $x<b$ iff $c2^{x+1}+2^x \leq k <(c+1)2^{x+1} $ for some constant $c.$
This post has been edited 6 times. Last edited by Sepled, Jun 4, 2020, 3:06 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
william122
1576 posts
#11
Y by
WLOG $\gcd(a,b)=1$. Suppose that, for some pair $(a,b)$ with $a<b$ we needed operation (ii) an infinite number of times.

The key idea is that, if we start from a given position and want to reach an endstate, we can permute the steps to reach the endstate as long as the permutation is still executable (i.e. when only operate on $k$ when there are at least 2 $k$s). In particular, this means that, if we needed step (ii) an infinite number of times, we can consider our endstate to be a turn far in the future right before the $N+1$st execution of step (ii) for $N\gg 1$.

Rearranging, we now start with $2N$ $0$s, and our endstate occurs when no pairs are left. Using at most $2^i$ $0$s, we can get at least $1$ of each of the numbers $b,2b,\ldots, ib$. Similarly, we can use finite number of steps to get $ka+b,ka+2b,\ldots, ka+ib$. Varying $k$, we can cover all residues mod $b$, so that means using finite $0$s, we can get $b$ consecutive numbers. Now, duplicate the necessary steps such that there are at least $2$ of the first $a$ consecutive numbers.

So, if we set $N$ to be a sufficiently large integer, which is possible because we assumed we applied (ii) an infinite number of times, we can get, by rearranging the appropriate steps, some multiset of numbers of the form $k+\{1,1,2,2,\ldots, a,a,a+1,a+2,\ldots b\}$. However, if we operate on $k+1$, we get $k+1+\{1,1,2,2,\ldots, a,a,a+1,a+2,\ldots b\}$. Hence, this pattern is self sustaining, and will never run out of pairs. Hence, there will never be an $N+1$st execution of step (ii) and we have a contradiction, as desired.
This post has been edited 1 time. Last edited by william122, Jun 12, 2020, 9:16 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Kayak
1298 posts
#12 • 2 Y
Y by Mango247, Mango247
sketch
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
squareman
966 posts
#13 • 3 Y
Y by Catsaway, teasaffrontaffy, centslordm
This one's a mindbender.

Scale $a,b$ down so that $\gcd(a,b) = 1.$

Claim: Suppose we start from a position and apply a sequence $S$ of $k$ moves of type (i), $A_1,A_2, \dots A_k,$ until we get to an "end position" where we must apply a (ii) move. If we apply an arbitrary sequence $B_1,B_2, \dots $ of type (i) moves on the same starting position, we will get to the same end position.

Proof: We induct on $N$ with base case trivial. For the inductive step, if $B_1$ consists of replacing $(x,x)$ with $(x+a,x+b);$ then take the first move $A_i$ consisting of replacing $(x,x)$ with $(x+a,x+b)$ (there must exist one, otherwise $S$ wouldn't lead to an end position).

Move $A_i$ to the front of $S.$ Note that 1) all moves are still valid since the $x$'s were not moved on before $A_i$ 2) the end position is unchanged 3) we still cannot possibly reach an end position before $A_k.$ Then apply the inductive hypothesis. $\square$

Critical Claim: Apply a sequence $S$ of moves from the empty board leading to an end position after making $N$ type (ii) moves. Assume we start with $2N$ zeros and make type (i) moves arbitrarily. Then we will reach the same end position.

Proof: Follow the same sequence $S$ on the $2N$ zeros, if we get to a type (ii) move then skip it; let the next move be on two zeros that haven't been moved on. This leads to the same end position. Then apply the previous claim. $\square$

The key insight is that it suffices to show that starting with enough zeros, there exists a sequence of moves allowing us to make (i) moves indefinitely (note the critical claim gives the freedom to choose any arbitrary sequence of (i) moves). It is not hard to see that with enough $0$s, we can get any large enough linear combination of $a$ and $b$ on the board.

So we can get a multiset of numbers of the form $$\{C+1,C+1,C+2,C+2,\ldots, C+a,C+a,C+a+1,C+a+2,\ldots C+b\}$$for an integer $C$ on the board. We always move on the two smallest integers in this set; we can do this indefinitely. $\blacksquare$
This post has been edited 4 times. Last edited by squareman, Jan 3, 2022, 2:34 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
L567
1184 posts
#14
Y by
Suppose not. First, note that the we don't have a "choice" in operation (i), irrespective of what order we do operations in, we get the same result eventually. This is because suppose you want to do some operations and instead I want to perform operation (i) on say $x,x$. Clearly your set of operations will eventually have to do operation (i) on $x,x$ as otherwise you will never have to use operation (ii), and when you do so, assume we operate on this pair, so it doesn't matter, the same thing works if I want to perform operation (ii) since I can just "wait" until you're done with operations on the rest and then since you can't go on infinitely, you will have to perform operation (ii) later.

Now start the game with $2^M$ times of operation (ii), I claim that this will go on forever. Let $a \ge b$, it suffices to show that there exist a consecutive set of $a$ numbers, each of which appear at least $2$ times, since then for any number bigger than it, say $n$, $n-a$ and $n-b$ appear each at least two times, so each contributes at least $1$ time of $n$ appearing so $n$ also appears at least two times and so on, so we never have to use operation (ii) beyond this.

Assume $a,b$ are coprime since otherwise we can just divide everything out by the gcd. There must exist a number $C$ such that every number bigger than $C$ can be written as $ap + bq$ for $p,q \ge 0$, by say chicken mc-nugget. Consider the $a$ numbers $C+1, C+2, \cdots, C+a$, so to each of them, there is a "path" from $0$ to them, and since the number of times it is written at most halves along each time you walk on the path, if we start with $> 2^{\frac{C+a}{a} + 1}$ things, then each of these numbers will get written at least twice, so we are done by the above paragraph. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
302 posts
#15
Y by
I think I have a solution, but I find that it is very difficult to put into words. I will do my best. (This solution is also potentially wrong, please catch any mistakes pls)

First, notice that the order of the moves does not change anything. Thus, we will have total control of the order of the moves. Second, it does not matter when we put a $0$ as long as we never miss any, you can write a $0$ before it is needed and it will not affect anything. Finally, if there are more $0$'s written than needed, this is a strictly stronger version of the setup. If the result can be shown for this arrangement it can be shown for the weaker one too.

So assume wlog $a<b$. We will denote $S_1=\{ a,b \}$ and define $S_n$ Inductively. If we have $S_{n-1}$ on the board, we can add $S_1$ to the board. Adding another $S_1$ gives $S_{n-1}$ and $S_{2}$ on the board. Keep adding $S_1$'s and combining until we have two $S_{n-1}$'s. Now, we can form an $S_n$. Notice that since there are now two $S_{n-1}$'s on the board, we can pair their elements and apply the operation. Thus, the sets $S_{n-1}+a$ and $S_{n-1}+b$ will be on the board. Now, proceed to pair numbers arbitrarily until we reach all numbers being distinct. To show that we will use (ii) finitely often, it is sufficient to show there are finitely many $S_i$'s.

It is easy to see by induction that $\min(S_k)=ak$, $\max(S_k)=bk$, and $|S_k|=2^k$. But, all elements in $S_k$ are distinct. So, \[ k(b-a) \geq 2^k \]Which is not true for sufficiently large $k$. Thus, finitely many $S_i$'s exists as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JAnatolGT_00
559 posts
#16 • 1 Y
Y by Mango247
Assume the opposite - for some $a<b$ we have to use operation ($ii$) for infinitelty many times.


Lemma 1. Assume there is a sequence of moves $p_1,p_2,\dots,p_k$ type ($i$) which lead from some intial configuration of numbers on board to the final configuartion, in which no moves of type ($i$) are possible. Then any arbitrary sequence of moves $q_1,q_2,\dots$ type ($i$) from the same initial configuration will lead to the same final configuration.
Proof. Induct on $k;$ the base case $k=0$ is trivial. Notice that due to our assumption sequence $q_i$ must end at some point. Now suppose that $q_1$ replaces $(x,x)\rightarrow (x+a,x+b)$ $(\star );$ in particular the initial configuration of numbers contain two copies of $x,$ so some move $p_n$ has to make replacing $(\star)$. If we take the first such move, then the sequence $$p_n,p_1,p_2,\dots,p_{n-1},p_{n+1},\dots ,p_k$$lead to the same final configuration as $p_i.$ It suffices to apply inductive step for configuration appeared after $q_1$ $\Box$


Lemma 2. Assume there is a sequence $r_i$ of moves starting from an empty board, which contains $k$ moves of type ($ii)$ and lead to some final configuration. Then the arbitrary sequence of moves type ($i$) starting from configuration of $2k$ zeroes will lead to the same final configuartion.
Proof. For a configuration of $2k$ zeroes apply moves $r_i$ missing all of type ($ii$) - then the lemma 1 finishes $\Box$


Due to the lemma 2 we may thought starting from sufficently large number of zeroes. One may obtain configuration $$X+1,X+2,\dots ,X+a,X+1,X+2,\dots ,X+b$$for $X=ab-a-b$ with some sequence of moves type ($i$), because of Chicken McNugget theorem. Easy to see that next we have to perform moves ($i$) for infinitely many times, contradiction $\blacksquare$
This post has been edited 2 times. Last edited by JAnatolGT_00, Dec 31, 2022, 5:15 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SHZhang
109 posts
#17
Y by
Assume without loss of generality that $\gcd(a, b) = 1$, since we may remove the common factor simply by dividing each number even written on the blackboard by it. Suppose for contradiction that operation (ii) is performed infinitely many times in a sequence of operations. Define a round of operations to be a block of consecutive operations starting on a type (ii) operation and ending right before the next type (ii) operation. Note that each round is finite. Call the round begining with the $i$-th type (ii) operation the $i$-th round/round $i$, and say that a nonnegative integer $n$ is used when a pair of the number $n$ is chosen in operation (i).

Lemma 1: If $n$ is a nonnegative integer expressible as a linear combination $n = ax + by$ with $x$ and $y$ nonnegative integers, then $n$ is used infinitely many times.
Proof: Strong induction on $n$. Base case $n=0$ follows from operation (ii) being performed infinitely many times, and the fact that after an operation (ii), 0 must be used before the next round can begin. For the inductive step, notice that at least one of $n-a$ and $n-b$ already satisfies the lemma. Assume without loss of generality that $n-a$ is. Then, every time $n-a$ is used, an additional copy of $n$ appears on the board, and this will occur infinitely often. Every two copies of $n$ will force $n$ to be used before the current round ends. Since each round is finite, the process will repeat in a future round and this will continue forever, proving the claim. $\square$

Lemma 2: If $n \ge \max(a, b)$ is an integer, $n-a$ is used in round $x$, and $n-b$ is used in round $y$, then there is some round $z$, between $x$ and $y$ (both inclusive), where $n$ is used.
Proof: Assume without loss of generality that $x \le y$. Then, after $n-a$ is used during round $x$, there exists a copy of $n$ on the board. If $n$ is never used from round $x$ to round $y$, then we cannot lose any copies of $n$, and on round $y$, we will gain a second copy of $n$. But we must use the two copies of $n$ before round $y$ ends, contradicting the fact that we are not using $n$ from round $x$ to round $y$. $\square$

To finish, note that all sufficiently large integers (everything greater than $ab - a - b$, to be precise) satisfy the hypothesis of lemma 1, so they are used in some round. Then we can find $\max(a, b)$ consecutive integers that are used during some round. Let $R$ be an integer such that on or before round $R$, all these consecutive integers have been used at least once. Then by lemma 2, the number following these consecutive integers must be used sometime during or before round $R$, and the number following it, and so on forever. Therefore infinitely many integers must be used in some round up to $R$, contradicting the fact that each round is finite.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AdventuringHobbit
164 posts
#18
Y by
Pretty easy for C6 (and way easier than C4, C5). First observe that the order in which we apply our two operations does not matter. WLOG $\gcd(a,b)=1$, otherwise we can just divide by the common gcd and have an equivalent problem. Now by chicken mcnugget theorem, for any number $k>ab-a-b$, we will be able to get a $k$ by applying the first operation given we are supplied with sufficiently many $0$'s. Observe that it now suffices to show we can find a multiset of integers, such that when the first operation is applied some nonzero number of times the multiset is shifted. WLOG $a<b$. Let a "snowstorm" be the operation formed by finding the smallest value $k$ that is in a pair, and applying the first operation to every $k$ on the board. I claim that we can find a multiset that is right shifted by $1$ after applying a snowstorm. Represent our multiset with a $b$ dimensional vector containing the multiplicities of the smallest element, the number one more than the smallest element, the number two more than the smallest element, and so on. Then the vector consisting of $a$ $2$'s and $b-a$ $1$'s fits the bill.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1482 posts
#19
Y by
Groupsolved with leo.euler. More of a pain to writeup than actually solve.

Claim: We can make infinite moves given the board (as a multiset) $\mathcal{L} = \{0, a, \dots, (b-1)a\} \cup \{0, b, \dots, (a-1)b\}$
Proof. We can repeatedly apply the operation involving the $0$ to the first set in the union until we get $\{b, a + b, \dots, (b-1)a + b, ba\} \cup \{b, \dots, (a-1)b\}$.
However, this is equivalent to shifting the entire board up by $b$. $\blacksquare$
Note that by considering the operation as removing two occurences of $n$ and adding one occurence of $n + a$ and $n + b$, the operation becomes commutative besides a positivity condition.
Now, FTSOC suppose that its possible to do $(ii)$ infinite times in some order.

Claim: Each number $ma + nb$ appears infinitely many times.
Proof. Follows inductively. $\blacksquare$

Claim: This implies that this is also possible for a board containing $\mathcal{L}$ to have infinite occurences of $(ii)$.
Proof. Wait until $(ii)$ has been done $N$ times and needs to be done for an $N+1$ times for an arbitrarily large $N$.
Then rearrange the moves such that $(ii)$ is done $N$ times in the beginning. It follows that the final config must be unique by greedily running $(i)$ until unable to do so, and counting the number of times $(i)$ is done to each number.
In other words, given an intermediary config, we can reach the final config as well.
We simply then take a large enough $N$ such that we can fully embed $\mathcal{L}$ in the board position as an intermediary config. $\blacksquare$
It remains to do some formalities about the order of operations.

Claim: Any board containing $\mathcal{L}$ has finitely many occurences of $(i)$.
Proof. FTSOC suppose that its possible to run out of the ability to do $(i)$ on such a board after finitely many moves.
Since $(i)$ must be run at least once on $0$, we can move the occurence of $(i)$ at $0$ to be the very first move afterwards while respecting positivity.
This creates a new occurence of $a$ and $b$ immediately afterwards, which must also have $(i)$ ran on them at some point. We can then shift up the move involving $(i)$ on $a$ while respecting positivity. Repeating this in the order of the first arguement on $\mathcal{L}$, we end up requiring infinitely many moves through simply reordering, contradiction. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leo.Euler
577 posts
#21
Y by
Solved with YaoAoPS.
WLOG $\gcd(a, b)=1$. Assume for contradiction that we apply operation (ii) infinitely many times. Essentially, a configuration can be seen as a multiset of lattice points in the first quadrant, by ignoring $a$ and $b$. What I mean by this is that if we take $a$ and $b$ arbitrary then a given configuration is a process on lattice points that represent linear combinations of $a$ and $b$ in an obvious way. View two points as equivalent if they have the same signature, and use this as an equivalence class for the points. This process starts with the origin, and operations (i) and (ii) are applied following the rules.

Lemma: The order in which operations (i) and (ii) are applied doesn't matter after a sufficient number of moves are applied.
Proof. Consider the coordinate setup as previously described. We consider the points corresponding to the configuration. The idea is that
  • adding by $a$ corresponds to moving $1$ unit right and adding by $b$ corresponds to moving $1$ unit up, and
  • any two coordinates are equivalent iff there exists a sequence of ``knight" moves of the form $(\pm a, \mp b)$ between them.
Operation (i) corresponds to up-right moves applied to points sufficiently far from the origin (and we eventually cover two or more distinct points with the same signature), while operation (ii) corresponds to adding another point at the origin. Thus we can eventually ``shuffle" the order of operations and result in the same set of points.
:yoda:

Claim: We can apply infinite moves on the configuration given by $\{0, a, \dots, (b-1)a\} \sqcup \{0, b, \dots, (a-1)b\}$.
Proof. Apply operation (i) repeatedly using the $0$ in $\{0, a, \dots, (b-1)a\}$. Essentially this shifts all the coordinates $1$ unit up. Thus we can apply infinite moves on the configuration.
:yoda:

The final fact we require is that by the means of knight moves we have infinitely many equivalence classes.

Now by the lemma let there be an infinite pile of $(0, 0)$ points, and apply operation (i) any number of times. Then using the coordinates it is easy to construct the set in the claim via a sequence of right moves and up moves, so by the claim we are done.

Remark: I think the main ideas involved in this problem are fairly natural, and in fact everything can be written up with respect to the coordinate setup. The ``Chicken McNugget" idea here is essentially the same thing as not being able to move from $(-1, a-1)$ to the first quadrant by a series of knight moves, which was used in a number of other solutions.
This post has been edited 1 time. Last edited by Leo.Euler, Jan 5, 2024, 6:14 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
4999 posts
#22 • 1 Y
Y by Cookierookie
silly goofy problem


WLOG let $\gcd(a,b)=1$ and $a<b$. View the problem as follows: we have a number line indexed by the nonnegative integers. If any exist, we take some nonnegative integer $n$ with at least $2$ stones on it, and move them to $n+a$ and $n+b$. Otherwise, we add two stones to $0$. We wish to show that finitely many stones get added.

Suppose that no matter what, infinitely many stones get added, so there are infinitely many points where every point on the number line has at most $1$ stone. Consider one of these points and suppose that $2N$ stones are present in total at this point. Then change the situation slightly: instead of adding stones to $0$, we start with $2N$ stones on $0$ and move them in any way we want, but don't add any new stones to $0$. Evidently if we make two moves from different integers $n_1,n_2$ in that order such that $n_2$ has at least $2$ stones before we move from $n_1$, we could swap their order and nothing after these two moves changes. Therefore, it is clear that by starting with any previously "valid" series of moves (i.e. one where we only move from $0$ if there are no other options) we can reach any series of moves, without the condition on moves from $0$ (for example, we could start by moving $N$ times from $0$), such that these two series produce the same ending position—in particular, this means that we can make any series of moves without "the condition" and it will terminate. Call this new set of rules—namely fixing a positive integer $N$, placing $2N$ stones on $0$, and making whatever moves we want—the "modified" version.

If we start with enough stones at $0$ and make an appropriate series of moves, we can get a number onto anything of the form $ax+by$, where $x,y$ are nonnegative integers. By Chicken McNugget, every integer greater than $ab-a-b$ can be written in this form. Thus if we make $N$ large enough and perform the appropriate moves in the "modified" version, we can get at least $2$ stones on each of $m,\ldots,m+a-1$ and at least $1$ stone on each of $m+a,\ldots,m+b-1$ for some large enough $m$. But from this state we can make infinitely many moves without adding any more stones to $0$ by moving from $m$, then $m+1$, then $m+2$, and so on. This contradicts our assumption that any sequence of "modified" moves starting with $2N$ stones on $0$ must terminate.
This post has been edited 1 time. Last edited by IAmTheHazard, Oct 23, 2023, 6:33 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1664 posts
#23
Y by
Without loss of generality, let $a<b$ and $\gcd(a,b)=1.$ The configuration of the problem clearly prompts us to consider an alternate formulation of the problem. The following infinite process takes place on an initially empty coordinate grid.
  1. If there are two stones at the same point on the grid or differ by some integer multiple of $(b,-a)$, we move one up by $1$ and one right by $1$.
  2. If moves of the above form is not possible, then drop two stones at the origin.
Clearly, a stone at $(x,y)$ represents a number at $ax+by$. It is clear that the location of a stone depends only on the nature of the moves made on it, including its birth, and not the order they were made in. In particular, if we assume for the contradiction that $(ii)$ is applied infinitely many times, then we can simply add an infinite number of stones at the origin. Hence, if we consider the configuration with a stone on each of the points $(0,1)$, $(0,2)$, $\dots$, $(0,a-1)$ and $(1,0)$, $(2,0)$, $\dots$, $(b-1,0)$, we can use the infinitely many origin stones to move everything up by one, contradiction! Since we can place infinitely many zeroes, we can always reach a configuration of this form since by the Chicken McNugget theorem we can make all sufficiently large numbers.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asdf334
7574 posts
#24 • 1 Y
Y by OronSH
same as #4

First assume $\gcd{(a,b)}=1$ and $b>a$. Each integer on the board can be represented by $Xa+Yb$ with $Y\in \{0,\dots,a-1\}$.

Consider the infinite lattice grid of points $(x,y)$ where $x\ge 0$ and $y\in \{0,\dots,a-1\}$. At each point $(X,Y)$ we assign a frequency of numbers $Xa+Yb$ on the board.

Then the initial state is all zeros. Operation $(i)$ performs the following on a point $(x,y)$ with value at least $2$:
If $y<a-1$, take
\[(x,y),(x,y)\to (x+1,y),(x,y+1).\]If $y=a-1$, take
\[(x,y),(x,y)\to (x+1,y),(x+b,0).\]Operation $(ii)$ simply adds $2$ to the value at $(0,0)$.

Suppose that there is a sequence of moves in which operation $(ii)$ is applied infinitely many times. Consider the state after $2^{b-1}-1$ operations of $(ii)$ followed by arbitrary operations of $(i)$ until no such operations are possible. Trivially all values are either $0$ or $1$. The value at $(0,0)$ is clearly $0$ since all operations preserve the parity of this value.

Claim: The values at $(1,0),\dots,(b-1,0)$ are all $1$.
Proof: By the nature of operation $(i)$, the values at $(r,0)$ for $r\in \{1,\dots,b-1\}$ may only be incremented through the step
\[(r-1,0),(r-1,0)\to (r,0).\]Evidently we begin with a value of $2^b-2$ at $(0,0)$. Then for each $r\in \{1,\dots,b-1\}$, we perform operation $(i)$ a total of $2^{b-r}-1$ times at $(r-1,0)$. We can now verify that all said values are equal to $1$. $\blacksquare$

Claim: The values at $(0,1),\dots,(0,a-1)$ are all $1$.
Proof: The proof is essentially verbatim as the one above. It is important, however, that $b>a$. $\blacksquare$

It turns out that this is sufficient. Perform the $2^{b-1}$th operation of $(ii)$. The following claim is that operation $(i)$ may now be performed indefinitely, providing the desired contradiction.

Claim: Operation $(i)$ must be performed at every point $(x,y)$ in the infinite lattice grid.
Proof: Split the lattice grid into blocks: block $k\ge 0$ consists of lattice points $(x,y)$ where $x\in [kb,(k+1)b)$. We use induction to prove the claim.

The base case is proven through yet another induction, this time on $y$ from $0$ to $a-1$. At the end, each point in block $0$ is exhausted. In addition, the original frequencies ($2$ at $(0,0)$, and $1$ at the "axes") have been maintained, but the $x$-coordinates have been incremented by $b$.

The increment is enough to complete our induction, as we have achieved the exact same configuration within block $k+1$. This may also be thought of through the following argument: for $k\ge 0$, the residue from performing operation $(i)$ on block $k$ provides the jump-start for operation $(i)$ in the next block $k+1$.

We are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
DottedCaculator
7303 posts
#25 • 1 Y
Y by centslordm
WLOG $\gcd(a,b)=1$ and $a<b$. Notice that the order of the operations does not matter. Let $n$ be large. Write $0$ $2n$ times. We claim that operation $1$ can always be done. By the Chicken McNugget Theorem, there exists $c$ such that $c+1$, $\ldots$, $c+b$ are linear combinations of $a$ and $b$. Then, we can get at least $2$ copies of $c+1$, $\ldots$, $c+a$ and at least one copy of $c+a+1$, $\ldots$, $c+b$ for large $n$. Now, we can do operation $1$ infinitely by operating on $c+1$, then increasing $c$ by $1$, which allows us to repeat the process infinitely.
Z K Y
N Quick Reply
G
H
=
a