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
Interesting inequalities
sqing   1
N a minute ago by sqing
Source: Own
Let $ a,b>0 $ and $ a+b\leq 1  $ . Prove that
$$\left(\frac{1}{a^3}-1\right)\left(\frac{1}{b^3}-1\right)-k\left(\frac{a}{b}+\frac{b}{a}\right) \geq 49-2k$$Where $24\geq k\in N^+.$
$$\left(\frac{1}{a^3}-1\right)\left(\frac{1}{b^3}-1\right) \geq 49$$$$\left(\frac{1}{a^3}-1\right)\left(\frac{1}{b^3}-1\right)-25\left(\frac{a}{b}+\frac{b}{a}\right) \geq -\frac{13}{12}$$$$\left(\frac{1}{a^3}-1\right)\left(\frac{1}{b^3}-1\right)-26\left(\frac{a}{b}+\frac{b}{a}\right) \geq -\frac{10}{3}$$$$\left(\frac{1}{a^3}-1\right)\left(\frac{1}{b^3}-1\right)-27\left(\frac{a}{b}+\frac{b}{a}\right) \geq -\frac{23}{4}$$
1 reply
+1 w
sqing
5 minutes ago
sqing
a minute ago
Calculus
youochange   14
N 22 minutes ago by Moubinool
Find the area enclosed by the curves $e^x,e^{-x},x^2+y^2=1$
14 replies
1 viewing
youochange
Yesterday at 2:38 PM
Moubinool
22 minutes ago
Interesting inequalities
sqing   2
N 37 minutes ago by sqing
Source: Own
Let $ a,b>0 $ and $ a+b\leq 1  $ . Prove that
$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-k\left(\frac{a}{b}+\frac{b}{a}\right) \geq 225-2k$$Where $104\geq k\in N^+.$
$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right) \geq 225 $$$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-106\left(\frac{a}{b}+\frac{b}{a}\right) \geq \frac{155}{12}$$$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-108\left(\frac{a}{b}+\frac{b}{a}\right) \geq \frac{26}{3}$$$$\left(\frac{4}{a^2}-1\right)\left(\frac{4}{b^2}-1\right)-110\left(\frac{a}{b}+\frac{b}{a}\right) \geq \frac{17}{4}$$
2 replies
1 viewing
sqing
an hour ago
sqing
37 minutes ago
Combi Geo
Adywastaken   3
N 39 minutes ago by TUAN2k8
Source: NMTC 2024/8
A regular polygon with $100$ vertices is given. To each vertex, a natural number from the set $\{1,2,\dots,49\}$ is assigned. Prove that there are $4$ vertices $A, B, C, D$ such that if the numbers $a, b, c, d$ are assigned to them respectively, then $a+b=c+d$ and $ABCD$ is a parallelogram.
3 replies
Adywastaken
Yesterday at 3:58 PM
TUAN2k8
39 minutes ago
No more topics!
IMO 2023 P3
799786   53
N Feb 22, 2025 by ihatemath123
Source: IMO 2023 P3
For each integer $k\geq 2$, determine all infinite sequences of positive integers $a_1$, $a_2$, $\ldots$ for which there exists a polynomial $P$ of the form \[ P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0, \]where $c_0$, $c_1$, \dots, $c_{k-1}$ are non-negative integers, such that \[ P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k} \]for every integer $n\geq 1$.
53 replies
799786
Jul 8, 2023
ihatemath123
Feb 22, 2025
IMO 2023 P3
G H J
G H BBookmark kLocked kLocked NReply
Source: IMO 2023 P3
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
799786
1052 posts
#1 • 19 Y
Y by beansenthusiast505, aidan0626, math90, Rounak_iitr, Loppukilpailija, LoloChen, GHHardy911, GeoKing, TheBarioBario, NO_SQUARES, SatisfiedMagma, Rg230403, Amir Hossein, megarnie, Math.1234, Schur-Schwartz, qlip, abc_978, cubres
For each integer $k\geq 2$, determine all infinite sequences of positive integers $a_1$, $a_2$, $\ldots$ for which there exists a polynomial $P$ of the form \[ P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0, \]where $c_0$, $c_1$, \dots, $c_{k-1}$ are non-negative integers, such that \[ P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k} \]for every integer $n\geq 1$.
This post has been edited 7 times. Last edited by v_Enhance, Sep 23, 2023, 2:16 AM
Reason: fix latex pet peeves
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aidan0626
1909 posts
#2 • 2 Y
Y by Rounak_iitr, cubres
For each integer $k\geqslant 2,$ determine all infinite sequences of positive integers $a_1,a_2,\dots$ for which there exists a polynomial $P$ of the form $P(x)=x^k+c_{k-1}x^{k-1}+\cdots c_1 x+c_0,$ where $c_0,c_1,\dots,c_{k-1}$ are non-negative integers, such that
$$P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$$for every integer $n\geqslant 1.$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
navi_09220114
479 posts
#3 • 81 Y
Y by GrantStar, Aryan-23, ihatemath123, weedtaker567, 799786, Dem0nfang, khan.academy, aidan0626, Tintarn, math90, InternetPerson10, djmathman, Supertinito, David-Vieta, numbersandnumbers, Therealway, Hexagrammum16, psi241, godjuansan, melowmolly, Anzoteh, Aoxz, TRAN THAI HUNG, steppewolf, MathLover_ZJ, MS_Kekas, qwedsazxc, PRMOisTheHardestExam, GioOrnikapa, L567, Supercali, Aimingformygoal, Creeper1612, NO_SQUARES, Assassino9931, Cty-circle, centslordm, LoloChen, Quidditch, EpicBird08, Plasma_Vortex, Filipjack, samrocksnature, megahertz13, RobertRogo, Orthogonal., Seicchi28, smartvong, Justpassingby, QWER001, ilikecats07, Rg230403, somebodyyouusedtoknow, OronSH, abrahms, rg_ryse, amir_rh, mathleticguyyy, Amir Hossein, Ankoganit, pavel kozlov, FOL, CyclicISLscelesTrapezoid, Joider, MathFan335, kamatadu, Rounak_iitr, TemetNosce, Eulermathematics, egxa, Sedro, abc_978, qiu-, stayhomedomath, qlip, DensSv, ehuseyinyigit, MS_asdfgzxcvb, cubres, giangtruong13, Mysteriouxxx
My proposal :>

Authorship comments
This post has been edited 22 times. Last edited by navi_09220114, Jul 8, 2023, 2:13 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
799786
1052 posts
#4 • 2 Y
Y by Rounak_iitr, cubres
I think that this problem can be rephrased as a recurrence sequence, with:
$a_{n+k}=\frac{P(a_n)}{a_{n+1}...a_{n+k-1}}$
So now you only need to find ALL $P(x),a_1,a_2,...,a_{k}$ so that every following terms are integers
(And even worse, this is very tedious)
However, there is a weakness: You can prove by induction that:
$a_x=\frac{a_{x-k}P(a_{x-k})}{P(a_{x-k-1}}$
This post has been edited 3 times. Last edited by 799786, Jul 8, 2023, 6:12 AM
Reason: continue the idea
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
numbersandnumbers
258 posts
#5 • 9 Y
Y by Rushery_10, PRMOisTheHardestExam, Manteca, asdf334, AutomatiC__, scnwust, Rounak_iitr, Sneakyturtle, cubres
The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$. These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$. Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
\[a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}\]and for $n > 1$, $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$.

First, let's handle the special case $P(x) = x^k$; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$. Then, if $a_n = b$, we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$; therefore $a_{n+1} = b$. Therefore the sequence is eventually constant at $b$; by applying $(\star)$ we get that $a_n = b$ for all $n$, as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$, we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$. Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$, there are only finitely many $n$ with $a_n = m$.
Proof. For every such $n$, we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$. Thus, if there are infinitely such $n$, we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$. By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$.
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$. But then,
\[1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},\]so $a_{n+k+1} < a_{n+1}$. Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$, which must be less than $m$, and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$, we find that $a_{n'-1} > a_{n'} = m'$, contradicting the minimality of $m$. $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$, so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$. But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$, so there must be one, call it $(d_1,\ldots,d_{k+1})$, which appears infinitely many times. Then we must have
\[P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})\]for infinitely many $n$. By Lemma 2, this means that
\[P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})\]for infinitely many $x$, meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$. Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$, i.e. $d_i = id_1$ for all $i$. As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$, and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$. By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b +  (n-1)d_1$ for all large $n$. If $b > 0$, we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$. But then $a_n \cdots a_{n+k-1} < P(1)$, so there is no possibility for $a_{n-1}$. So we are done in this case as well. $\square$
This post has been edited 2 times. Last edited by numbersandnumbers, Jul 8, 2023, 7:12 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
M11100111001Y1R
121 posts
#6 • 1 Y
Y by cubres
I'm not sure! Even I don't know, I'm just guessing that the proposer of this problem is Mr. Safaei from Iran. Does anyone know the proposer?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
navi_09220114
479 posts
#7 • 21 Y
Y by khan.academy, JingheZhang, David-Vieta, MS_Kekas, colonel_ionut, egxa, Photaesthesia, LoloChen, TSandino, RobertRogo, khina, pavel kozlov, CyclicISLscelesTrapezoid, erringbubble, Mysteriouxxx, Illuzion, Sedro, qlip, damyan, cubres, aidan0626
I am the proposer [Ivan Chan from Malaysia]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
M11100111001Y1R
121 posts
#8 • 1 Y
Y by cubres
Congrats. it's a nice problem!
Thanks for telling that!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackmetalmusic
30 posts
#9 • 1 Y
Y by cubres
numbersandnumbers wrote:
The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$. These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$. Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
\[a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}\]and for $n > 1$, $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$.

First, let's handle the special case $P(x) = x^k$; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$. Then, if $a_n = b$, we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$; therefore $a_{n+1} = b$. Therefore the sequence is eventually constant at $b$; by applying $(\star)$ we get that $a_n = b$ for all $n$, as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$, we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$. Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$, there are only finitely many $n$ with $a_n = m$.
Proof. For every such $n$, we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$. Thus, if there are infinitely such $n$, we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$. By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$.
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$. But then,
\[1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},\]so $a_{n+k+1} < a_{n+1}$. Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$, which must be less than $m$, and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$, we find that $a_{n'-1} > a_{n'} = m'$, contradicting the minimality of $m$. $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$, so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$. But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$, so there must be one, call it $(d_1,\ldots,d_{k+1})$, which appears infinitely many times. Then we must have
\[P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})\]for infinitely many $n$. By Lemma 2, this means that
\[P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})\]for infinitely many $x$, meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$. Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$, i.e. $d_i = id_1$ for all $i$. As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$, and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$. By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b +  (n-1)d_1$ for all large $n$. If $b > 0$, we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$. But then $a_n \cdots a_{n+k-1} < P(1)$, so there is no possibility for $a_{n-1}$. So we are done in this case as well. $\square$

elegant solution sir
though I think this problem was kinda easy for imo#3.
it's more like a hard #2 or #5
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
naman12
1358 posts
#10 • 9 Y
Y by navi_09220114, PRMOisTheHardestExam, NO_SQUARES, YaoAOPS, Rounak_iitr, two_steps, axsolers_24, MS_asdfgzxcvb, cubres
Huh. This is actually surprisingly amazing of a problem and I'm honestly in love :love:.

Main Claim. The sequence $a_n$ is increasing.
Suppose $a_n$ is a minimum of the sequence (which is possible as this is an integral sequence). If $a_n<a_{n-1}$ and $n>1$,
\[a_{n+k}P(a_{n-1})=\prod_{i=n-1}^ka_i=a_nP(a_n)<a_nP(a_{n-1})\]as $P$ is monotonic, so $a_{n+k}<a_n$. This is clearly impossible, so thus for any minimum, all previous terms must be equal. In particular, the sequence $a_n$ is (not necessarily strictly) increasing. $\blacksquare$

To finish, simply note that there exists some $y$ such that $P(x)<(x+y)^k$; for example,
\[y>\text{max}\left(\frac{c_j}{\binom kj}\right)\]This implies that since $a_n\leq a_{n+1}<a_n+y$, we have
\[(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})\in [0,y]^{k+1}\]by the Pigeonhole Principle, some value $(a'_1,\ldots,a'_{k+1})$ appears infinitely often. Call $n$ good if $(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})=(a'_1,\ldots,a'_{k+1})$. Then,
\[P(x)=\prod_{j=1}^k\left(x+\sum_{i=1}^ja'_i\right)=\prod_{j=1}^k\left(x+\sum_{i=2}^{j+1}a'_i\right)\]for infinitely many values of $x$ (which comes from taking $x=a_n,a_{n+1}$ where $n$ is good), so thus these factors must be equal up to permutation. However, as $a'_i\geq 0$, we know $a'_i=a'_{i+1}$, so $a'_i$ is constant. This means that $a_i$ is an arithmetic sequence, and clearly it is a non-decreasing one.

Motivation
Remarks
A note on difficulty
This post has been edited 1 time. Last edited by naman12, Jul 8, 2023, 7:50 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
799786
1052 posts
#11 • 1 Y
Y by cubres
Uh, finally solved this problem. Since my solution is quite the same as #5, I'll just leave some thoughts here.
First, this was very fun to solve tho. Even though the solution is fairly short, it's not easy to find. I enjoyed this problem a lot, so I think this is a very appropriate P3 problem. Just wished this was a little harder :(
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
navi_09220114
479 posts
#12 • 2 Y
Y by Rounak_iitr, cubres
naman12 wrote:
Huh. This is actually surprisingly amazing of a problem and I'm honestly in love :love:.

Main Claim. The sequence $a_n$ is increasing.
Suppose $a_n$ is a minimum of the sequence (which is possible as this is an integral sequence). If $a_n<a_{n-1}$ and $n>1$,
\[a_{n+k}P(a_{n-1})=\prod_{i=n-1}^ka_i=a_nP(a_n)<a_nP(a_{n-1})\]as $P$ is monotonic, so $a_{n+k}<a_n$. This is clearly impossible, so thus for any minimum, all previous terms must be equal. In particular, the sequence $a_n$ is (not necessarily strictly) increasing. $\blacksquare$

To finish, simply note that there exists some $y$ such that $P(x)<(x+y)^k$; for example,
\[y>\text{max}\left(\frac{c_j}{\binom kj}\right)\]This implies that since $a_n\leq a_{n+1}<a_n+y$, we have
\[(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})\in [0,y]^{k+1}\]by the Pigeonhole Principle, some value $(a'_1,\ldots,a'_{k+1})$ appears infinitely often. Call $n$ good if $(a_{n+1}-a_n,a_{n+2}-a_{n+1},\ldots,a_{n+k+2}-a_{n+k+1})=(a'_1,\ldots,a'_{k+1})$. Then,
\[P(x)=\prod_{j=1}^k\left(x+\sum_{i=1}^ja'_i\right)=\prod_{j=1}^k\left(x+\sum_{i=2}^{j+1}a'_i\right)\]for infinitely many values of $x$ (which comes from taking $x=a_n,a_{n+1}$ where $n$ is good), so thus these factors must be equal up to permutation. However, as $a'_i\geq 0$, we know $a'_i=a'_{i+1}$, so $a'_i$ is constant. This means that $a_i$ is an arithmetic sequence, and clearly it is a non-decreasing one.

Motivation
Remarks
A note on difficulty

I really love your remarks there: its pretty much what I felt when I solved the problem - the properties are rather surprising for me as well!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Rg230403
222 posts
#13 • 2 Y
Y by PRMOisTheHardestExam, cubres
numbersandnumbers wrote:
The answer is all constant or ascending arithmetic sequences, i.e. $a_n = b + (n-1)d$ for positive integers $b$ and nonnegative integers $d$. These work since we can take $P(x) = (x + d)(x + 2d) \cdots (x + kd)$. Now we show that no others work.

Before we begin, we note that given $P$ and $k$ consecutive values $a_{n}, \ldots, a_{n+k-1}$ of the sequence, the rest of the sequence can be fully determined, since we have
\[a_{n+k} = \frac{P(a_n)}{a_{n+1}\cdots a_{n+k-1}}\]and for $n > 1$, $a_{n-1} = P^{-1}(a_n\cdots a_{n+k-1})$ (note that $P$ is increasing and hence injective on the positive integers). Call these two relations $(\star)$.

First, let's handle the special case $P(x) = x^k$; we aim to prove that the $a_n$ are constant. To see this, let $b$ be the minimum value attained by any $a_n$. Then, if $a_n = b$, we have that $a_{n+1} \cdots a_{n+k} = b^k$ but $a_{n+i} \geq b$ for all $i$; therefore $a_{n+1} = b$. Therefore the sequence is eventually constant at $b$; by applying $(\star)$ we get that $a_n = b$ for all $n$, as desired.

Now assume that some non-leading coefficient of $P(x)$ is positive. We prove a bunch of lemmas.

Lemma 1. The sequence $(a_n)$ achieves arbitrarily large values.
Proof. Since $P(x) > x^k$ for all positive integers $x$, we conclude that $\max\{a_{n+1},\ldots,a_{n+k}\} > a_n$ for all $n$. Iterating this proves the claim. $\blacksquare$

Lemma 2. For every $m$, there are only finitely many $n$ with $a_n = m$.
Proof. For every such $n$, we must have $a_{n+1},\ldots,a_{n+k} \leq P(m)$. Thus, if there are infinitely such $n$, we can find some $n < n'$ with $a_{n+i} = a_{n'+i}$ for all $1 \leq i \leq k$. By iterating $(\star)$ we get that $a_n$ is periodic, which contradicts Lemma 1. $\blacksquare$

Lemma 3. $a_{n+1} \geq a_n$ for all $n$.
Proof. Suppose not. Let $m$ be the minimum value such that there exists an $n$ such that $a_n > a_{n+1} = m$. But then,
\[1 > \frac{P(a_{n+1})}{P(a_n)} = \frac{a_{n+k+1}}{a_{n+1}},\]so $a_{n+k+1} < a_{n+1}$. Thus, if we let $m' = \min \{a_{n+2},\ldots,a_{n+k+1}\}$, which must be less than $m$, and $n'$ be the minimal $n+2 \leq n' \leq n+k+1$ with $a_{n'} = m'$, we find that $a_{n'-1} > a_{n'} = m'$, contradicting the minimality of $m$. $\blacksquare$

Lemma 4. $a_{n+1} - a_n = O(1)$
Proof. By Lemma 3, $a_{n+1}^k \leq a_{n+1} \cdots a_{n+k} = P(a_n)$, so $a_{n+1} - a_n \leq P(a_n)^{1/k} - a_n$. But this is bounded above. $\blacksquare$

By Lemma 4, there are now finitely many possibilities for the tuple $(a_{n+1} - a_n, a_{n+2}-a_n,\ldots,a_{n+k+1} - a_n)$, so there must be one, call it $(d_1,\ldots,d_{k+1})$, which appears infinitely many times. Then we must have
\[P(a_n) = (a_n + d_1) \cdots (a_n + d_k) \text{ and } P(a_n+d_1) = (a_n+d_2)\cdots (a_n + d_{k+1})\]for infinitely many $n$. By Lemma 2, this means that
\[P(x) = (x + d_1) \cdots (x + d_k) \text{ and } P(x+d_1) = (x+d_2)\cdots (x + d_{k+1})\]for infinitely many $x$, meaning that the relations above have to hold as polynomials. Now, by Lemma 3 we have $d_1 \leq \cdots \leq d_{k+1}$. Moreover, since a polynomial can be factored into linear factors in only one way, we conclude that $d_i = d_{i+1} - d_i$ for all $1 \leq i \leq k$, i.e. $d_i = id_1$ for all $i$. As a result, $P(x) = (x + d_1)\cdots(x + kd_1)$, and there exists an $n$ with $a_{n+i} = a_n + id_1$ for all $0 \leq i \leq k+1$. By iterating $(\star)$ forwards, we get that there exists an integer $b$ with $a_n = b +  (n-1)d_1$ for all large $n$. If $b > 0$, we can iterate $(\star)$ backwards and conclude. Otherwise, we can iterate $(\star)$ backwards to get some $n > 1$ with $a_n \leq d_1$. But then $a_n \cdots a_{n+k-1} < P(1)$, so there is no possibility for $a_{n-1}$. So we are done in this case as well. $\square$

This proof is really nice, I did not see the clever argument for Lemma 3 presented in this solution so I had the following solution:

I have skipped the proof of claims that the $a_i$ get arbitrarily large in the following writeup.

Let $s_1< s_2< \dots$ be an inifinite sequence such that $a_{s_i}\le a_{s_{i+j}}$ for all $j\in \{1,2,\dots k\}$. Now, $a_{s_i}^{k-1}(a_{s_i}+c_0+c_1+\dots c_{k-1})\prod\limits_{j=1}^k a_{s_{i+j}}\ge a_{s_i}^k$. Thus, $|a_{s_{i+j}}-a_{s_i}|\le c_0+c_1+\dots c_{k-1}$. Thus, from each $s_i$ term, consider the polynomial: $P_i(x)=\prod\limits_{i=1}^k (x+a_{s_i+j}-a_{s_i})$.



By infinite pigeonhole principle, infinitely many of these polynomials are the same. Let's call one such polynomial occuring infinitely many times $S_1(x)$. Now, for infinitely many values of $x$, we have $P(x)=S_1(x)$. Thus, $P(x)=(x+d_1)(x+d_2)\dots (x+d_k)$ for some $d_1, \dots d_k \ge 0$ and infinitely many times we have $a_{s_i}+d_j=a_{s_{i+j}}$ all occuring simultaneously. Let the infinite sequence of $s_i$ with previous property be $t_1<t_2 \dots$.

Now, $P(a_{t_i+1})=\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)$ and thus, \[a_{t_i+k+1}=\dfrac{\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)}{\prod\limits_{j=1}^k P(a_{t_i}+d_1+d_j)}\cdot a_{t_i+1}\]
Thus, again $a_{t_i+k+1}-a_{t_i+1}$ is bounded and we have that polynomials $Q_i(x)=\prod\limits_{j=1}^k(x+a_{t_i+j}-a_{t_i})$ have the same polynomial occuring infinitely many times. Thus, we get a polynomial $S_2(x)$ which occurs infinitely many times of the form $(x+r_1)(x+r_2)\dots (x+r_k)$ but this must be $P(x)$. Thus, ${d_1,d_2,\dots d_k}-{d_1}={0,d_1,\dots d_k}\setminus {d_t}$ for some $t$. Thus, the $d_i$ form an AP in some order with common difference $d_1$. Thus the polynomial is $(x+d)(x+2d)\dots (x+kd)$.

Now, for each $t_i$, consider the lowest $l_i$ such that $t_{i+l_i}-t_i\ne l_id$. If such $l_i$ exist infinitely often then amongst each of these, we again have that $|t_{i+l_i}-t_{i+l_i+j}|$ is bounded for $j\in \{1,2,\dots k\}$. Thus repeating our previous argument, we get that $t_{i+l_i+j}-t_{l_i} > 0$ for all $j$ but $t_{i+l_i}-t_i\ne l_i d$, thus we get that for some $j>l_i$, we have $t_{i+j}-t_{i+l_i} =l_id$ which implies $t_{i+j} \le t_{l_i+j}$ which is a contradiction.

Thus, such $l_i$ do not exist infinitely often. Thus, there is a term $t_i$ such that $a_{t_i+j}-a_{t_i}=jd$ for all $j\in {1,2,\dots k}$ and polynomial is $(x+d)(x+2d)\dots (x+kd)$ and using this we can induct on the sequence in both directions to find that if forms the required AP with common difference $d$. Thus, we are done!

I really liked the problem and don't really have much more to remark which is different from the previous comments. I do believe that it's on an easier side of P3s but that does not make it inappropriate for the position. The best way to judge is to just wait for the statistics to come out :)
This post has been edited 2 times. Last edited by Rg230403, Jul 8, 2023, 8:12 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Complete_quadrilateral
144 posts
#14 • 1 Y
Y by cubres
Claim 1:
$A$ is either unbounded or constant.
Proof
Claim 2:
$A$ is nondecreasing
Proof
So if $A$ is not constant we get that at some point all numbers after some $a_N$ are $a_N+O(1)$. Now if we have that set of $a_{N+k}-a_N$ is not always the same after some point we get that there are at least two of such sets appearing infinitely many times, call them $S$ and $S'$, so $P(x)=\Pi_{p\in S}(x+p)=\Pi_{q\in S'}(x+q)$, contradiction, so that set is fixed after some arbitrarily big $a_N$.
Claim: This set is an arithmetic progression
Proof
Now we know that $A$ is an arithmetic progression after some point so $P(x)=\Pi_{i=1}^{i=k} (x+ti)$. Now we can just go backwards and get that $A$ was an arithmetic progression all along.
Comment
This post has been edited 2 times. Last edited by Complete_quadrilateral, Jun 19, 2024, 7:20 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Anzoteh
126 posts
#15 • 4 Y
Y by PRMOisTheHardestExam, GeoKing, navi_09220114, cubres
navi_09220114 wrote:
It all started with a desperate need for NT problems in our country's TST lol. My friend Anzo gave me a bootleg of 2015 A1:

"Let $a_0$ be arbitrary postive real, $a_{n + 1} = \frac{(n + 2)a_n}{(a_n^2 + n + 1)}$. Determine $\lim_{n \rightarrow \infty} (a_1 + ... + a_n) - n$ in terms of $a_0$."

OMG I'm so honored to be featured by the proposer himself :-D

It is a very beautiful problem, and no, I haven't solved it yet. One more thing to add into my bucket list!
navi_09220114 wrote:
Meanwhile, the NT we used for the TST is here lol: (It's simple but nice so do try it!)

"Do there exist infinitely many triples of positive integers $(a, b, c)$ such that $a$, $b$, $c$ are pairwise coprime, and $a! + b! + c!$ is divisible by $a^2 + b^2 + c^2$?"

This was Malaysian TST P4 this year, and it's mine. (Could have been a borderline P5 tbh).
Z K Y
G
H
=
a