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
find angle
TBazar   0
2 minutes ago
Given $ABC$ triangle with $AC>BC$. We take $M$, $N$ point on AC, AB respectively such that $AM=BC$, $CM=BN$. $BM$, $AN$ lines intersect at point $K$. If $2\angle AKM=\angle ACB$, find $\angle ACB$
0 replies
TBazar
2 minutes ago
0 replies
Geometry
Lukariman   10
N 15 minutes ago by Captainscrubz
Given circle (O) and point P outside (O). From P draw tangents PA and PB to (O) with contact points A, B. On the opposite ray of ray BP, take point M. The circle circumscribing triangle APM intersects (O) at the second point D. Let H be the projection of B on AM. Prove that $\angle HDM$ = 2∠AMP.
10 replies
Lukariman
Tuesday at 12:43 PM
Captainscrubz
15 minutes ago
Simple inequality
sqing   21
N an hour ago by Bexultan
Source: JBMO 2011 Shortlist A3
$\boxed{\text{A3}}$If $a,b$ be positive real numbers, show that:$$ \displaystyle{\sqrt{\dfrac{a^2+ab+b^2}{3}}+\sqrt{ab}\leq a+b}$$
21 replies
sqing
May 15, 2016
Bexultan
an hour ago
Primes p such that p and p^2+2p-8 are primes too
mhet49   44
N an hour ago by MITDragon
Source: Albanian National Math Olympiad 2012
Find all primes $p$ such that $p+2$ and $p^2+2p-8$ are also primes.
44 replies
mhet49
Apr 1, 2012
MITDragon
an hour ago
Integer polynomial w factorials
Solilin   1
N 2 hours ago by Tkn
Source: 9th Thailand MO
Let $a_1, a_2, ..., a_{2012}$ be pairwise distinct integers. Show that the equation $(x -a_1)(x - a_2)...(x - a_{2012}) = (1006!)^2$ has at most one integral solution.
1 reply
Solilin
Yesterday at 2:12 PM
Tkn
2 hours ago
Combo NT
a_507_bc   4
N 2 hours ago by Namura
Source: Silk Road 2024 P1
Let $n$ be a positive integer and let $p, q>n$ be odd primes. Prove that the positive integers $1, 2, \ldots, n$ can be colored in $2$ colors, such that for any $x \neq y$ of the same color, $xy-1$ is not divisible by $p$ and $q$.
4 replies
a_507_bc
Oct 20, 2024
Namura
2 hours ago
Old hard problem
ItzsleepyXD   2
N 2 hours ago by ItzsleepyXD
Source: IDK
Let $ABC$ be a triangle and let $O$ be its circumcenter and $I$ its incenter.
Let $P$ be the radical center of its three mixtilinears and let $Q$ be the isogonal conjugate of $P$.
Let $G$ be the Gergonne point of the triangle $ABC$.
Prove that line $QG$ is parallel with line $OI$ .
2 replies
ItzsleepyXD
Apr 25, 2025
ItzsleepyXD
2 hours ago
Polynomial Factors
somebodyyouusedtoknow   1
N 3 hours ago by luutrongphuc
Source: San Diego Honors Math Contest 2025 Part II, Problem 2
Let $P(x)$ be a polynomial with real coefficients such that $P(x^n) \mid P(x^{n+1})$ for all $n \in \mathbb{N}$. Prove that $P(x) = cx^k$ for some real constant $c$ and $k \in \mathbb{N}$.
1 reply
somebodyyouusedtoknow
Apr 26, 2025
luutrongphuc
3 hours ago
I need the technique
DievilOnlyM   15
N 4 hours ago by sqing
Let a,b,c be real numbers such that: $ab+7bc+ca=188$.
FInd the minimum value of: $5a^2+11b^2+5c^2$
15 replies
DievilOnlyM
May 23, 2019
sqing
4 hours ago
Linear colorings mod 2^n
vincentwant   1
N 4 hours ago by vincentwant
Let $n$ be a positive integer. The ordered pairs $(x,y)$ where $x,y$ are integers in $[0,2^n)$ are each labeled with a positive integer less than or equal to $2^n$ such that every label is used exactly $2^n$ times and there exist integers $a_1,a_2,\dots,a_{2^n}$ and $b_1,b_2,\dots,b_{2^n}$ such that the following property holds: For any two lattice points $(x_1,y_1)$ and $(x_2,y_2)$ that are both labeled $t$, there exists an integer $k$ such that $x_2-x_1-ka_t$ and $y_2-y_1-kb_t$ are both divisible by $2^n$. How many such labelings exist?
1 reply
vincentwant
Apr 30, 2025
vincentwant
4 hours ago
sqrt(n) or n+p (Generalized 2017 IMO/1)
vincentwant   1
N 4 hours ago by vincentwant
Let $p$ be an odd prime. Define $f(n)$ over the positive integers as follows:
$$f(n)=\begin{cases}
\sqrt{n}&\text{ if n is a perfect square} \\
n+p&\text{ otherwise}
\end{cases}$$
Let $p$ be chosen such that there exists an ordered pair of positive integers $(n,k)$ where $n>1,p\nmid n$ such that $f^k(n)=n$. Prove that there exists at least three integers $i$ such that $1\leq i\leq k$ and $f^i(n)$ is a perfect square.
1 reply
vincentwant
Apr 30, 2025
vincentwant
4 hours ago
Flight between cities
USJL   5
N 5 hours ago by Photaesthesia
Source: 2025 Taiwan TST Round 1 Mock P5
A country has 2025 cites, with some pairs of cities having bidirectional flight routes between them. For any pair of the cities, the flight route between them must be operated by one of the companies $X, Y$ or $Z$. To avoid unfairly favoring specific company, the regulation ensures that if there have three cities $A, B$ and $C$, with flight routes $A \leftrightarrow B$ and $A \leftrightarrow C$ operated by two different companies, then there must exist flight route $B \leftrightarrow C$ operated by the third company different from $A \leftrightarrow B$ and $A \leftrightarrow C$ .

Let $n_X$, $n_Y$ and $n_Z$ denote the number of flight routes operated by companies $X, Y$ and $Z$, respectively. It is known that, starting from a city, we can arrive any other city through a series of flight routes (not necessary operated by the same company). Find the minimum possible value of $\max(n_X, n_Y , n_Z)$.

Proposed by usjl and YaWNeeT
5 replies
USJL
Mar 8, 2025
Photaesthesia
5 hours ago
A problem from Le Anh Vinh book.
minhquannguyen   0
5 hours ago
Source: LE ANH VINH, DINH HUONG BOI DUONG HOC SINH NANG KHIEU TOAN TAP 1 DAI SO
Let $n$ is a positive integer. Determine all functions $f:(1,+\infty)\to\mathbb{R}$ such that
\[f(x^{n+1}+y^{n+1})=x^nf(x)+y^nf(y),\forall x,y>1.\]
0 replies
minhquannguyen
5 hours ago
0 replies
IMO ShortList 1999, algebra problem 1
orl   42
N 6 hours ago by ihategeo_1969
Source: IMO ShortList 1999, algebra problem 1
Let $n \geq 2$ be a fixed integer. Find the least constant $C$ such the inequality

\[\sum_{i<j} x_{i}x_{j} \left(x^{2}_{i}+x^{2}_{j} \right) \leq C
\left(\sum_{i}x_{i} \right)^4\]

holds for any $x_{1}, \ldots ,x_{n} \geq 0$ (the sum on the left consists of $\binom{n}{2}$ summands). For this constant $C$, characterize the instances of equality.
42 replies
orl
Nov 13, 2004
ihategeo_1969
6 hours ago
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.
bhan2025
96 posts
#44 • 2 Y
Y by GeoKing, cubres
Main Claim) $a_1$ must be the minimum value of sequence $a$
pf) There obviously must exist a minimum value of sequence $a$, as the sequence is restricted to positive integers.
Assume $a_1$ is not the minimum. In other words, there exists $a_i$ ($i \neq 1$) such that $a_i$ is the minimum of $a$. Let $a_i$ be the first of such minimum values. Then, we can safely say that $a_{i-1} > a_i$.
We know that $P(a_{i-1}) = a_i a_{i+1} \ldots a_{i+k-1}$ and $P(a_i) = a_{i+1} a_{i+2} \ldots a_{i+k}$. Since $P(a_{i-1}) > P(a_i)$, this means that $a_i > a_{i+k}$.
However, since we set $a_i$ as the minimum value of $a$ this causes a contradiction.

Corollary of Main Claim) $a$ is a nondecreasing sequence
Explanation: Claim 1 essentially states that for any positive integer $n$, the minimum value of $a_{[n,\infty)}$ is $a_n$. Thus, using induction with $n = 1, 2, \ldots$ shows that $a$ must be nondecreasing.

We now split the proof into two cases:

$\textbf{Case 1}$) $a$ has a maximum value
This means that there exists some positive integer $n$ such that for all $i \geq n$, $a_i = w$ ($w$ is a constant)
Thus, $P(w) = w^k$, implying that $P(x) = x^k$. Therefore, $P(a_{n-1}) = (a_{n-1})^k = a_n a_{n+1} \ldots a_{n+k-1} = w^k$, which means that $a_{n-1} = w$. Repeating this logic for $n-2, n-3, \ldots, 1$ shows that $a_i = w$ for all $i$. We have obtained our first solution.

$\textbf{Case 2}$) $a$ doesn't have a maximum value
This means that sequence $a_i$ increases indefinitely as $i$ increases

Claim) $a$ is strongly increasing
Assume $a_i = a_{i+1}$ for some $i$. Since $P(a_i) = P(a_{i+1})$, we can see that $a_{i+1} = a_{i+k+1}$. Since $a$ is nondecreasing, this means that all numbers $a_i$ through $a_{i+k+1}$ are equal. Repeating this logic while increasing $i$ shows that $a$ becomes a constant sequence, causing a contradiction.

Let $Seq(i) = (a_{i+1}-a_i, a_{i+2} -a_i, \ldots, a_{i+k}-a_i)$. $Seq(i,j)$ denotes the $j$th element in the $k$-element permutation $Seq(i)$
Set $N$ as a very, very large positive integer. Then, we can safely say that all $a_i$ for $i>N$ is close to infinity as $a$ has no upper bound.

Claim 2) For all $i>N$ $Seq(i)$ must be a constant
pf) Assume $Seq(i) \neq Seq(i+1)$ for some very large $i > N$
Let $P_1(x) = \Pi_{j=1}^k (x + Seq(i)(j))$ and $P_2(x) = \Pi_{j=1}^k (x + Seq(i+1)(j))$.
Then, we can see that $P(a_i) = P_1(a_i)$ and $P(a_{i+1}) = P_2(a_{i+1})$. Since $P_1 \neq P_2$, at least one of the functions $P - P_1$ and $P - P_2$ cannot be a zero function with all coefficients equal to $0$. WLOG, assume that $P - P_1$ is nonnegative.
Since both $P$ and $P_1$ have nonnegative coefficients, $P - P_1$ cannot have any coefficients that are larger than $max(c_0,c_1,\ldots,c_{k-1})$. However, since we set $a_i$ as a very, very large positive integer it cannot be a solution of $P - P_1$. Thus, there is a contradiction.

Thus, $Seq(i)$ eventually becomes constant for $i > N$, which means $a$ must be an arithmetic sequence (this is trivial by induction working backwards from $N$ to $1$). We have obtained our second solution.

Note: The explanation for Claim 2 definitely could be improved (it is possible a very large negative coefficient in $P_1$ overrides the large value of $a_i$), but the intuition should be very clear.

Additional bound to address logical hole in Claim 2
Remarks on Question and Solution
This post has been edited 3 times. Last edited by bhan2025, Jul 14, 2023, 11:51 AM
Reason: last remarks
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Marinchoo
407 posts
#45 • 2 Y
Y by PRMOisTheHardestExam, cubres
Here's my submission at the IMO. I missed the slick finish from the official solution, though I think my approach is much more motivated. The answer is all infinite arithmetic progressions of positive integers. These work because if $a_{n} = \lambda_{1} + (n-1)\lambda_{2}$ for some integers $\lambda_{1} >0$, $\lambda_{2} \geq 0$ we can pick $P(x) = (x+\lambda_{2})(x+2\lambda_{2})\cdots(x+k\lambda_{2})$ and the polynomial identity will be satisfied. We show that no other sequences work.

Main claim. The key step is recognizing that the sequence $\{a_{i}\}_{i=1}^{\infty}$ is strictly increasing if it's not constant.

Proof: The idea is to show that if $d = \min_{m \in \mathbb{N}} a_{m}$ and there exists some $t > 1$ with $a_{t} = d$, then the sequence is constant. Assume that's not the case. If $a_{t-1} > d$, compare $P(a_{t-1})$ and $P(a_{t})$:
\[a_{t+1}a_{t+2}\cdots a_{t+k} = P(a_{t}) < P(a_{t-1}) = a_{t}a_{t+1}\cdots a_{t+k-1} \Longrightarrow a_{t+k} < a_{t} = d = \min_{m\in\mathbb{N}} a_{m}\]with the inequality holding true due to all the $c_{i}$ being nonnegative. The last inequality $a_{t+k-1} < d$ is clearly impossible, so we derive a contradiction in this case. If $a_{t-1} = d$, comparing $P(a_{t-1})$ and $P(a_{t})$ implies that $a_{t+k} = a_{t} = d$ and we just proved that if $a_{i} = d$ for $i>1$, then $a_{i-1} = d$ as well, we get that $a_{t-1} = a_{t} = a_{t+1} = \cdots = a_{t+k} = d$ by backwards induction from $a_{t+k} = d$. Repeating this argument for $a_{t}$ and $a_{t+1}$ we get that $a_{t+k+1} = d$ as well and continuing on forward, the sequence $\{a_{i}\}_{i>t-2}$ is constant. We can also show that the beginning of the sequence attains that same constant value:
\[a_{t-1}a_{t-1}\cdots a_{t+k-2} = P(a_{t-2}) \geq P(d) = P(a_{t-1}) = a_{t}a_{t+1}\cdots a_{t+k-1}\]However, the leftmost and rightmost expressions are both equal to $d^{k}$ which is possible only if $a_{t-2} = d$. Inducting downward, we get that $a_{t-3} = d$ and so on as well, so the sequence is indeed constant. Thus we've proven that $a_{1} = d$ and $a_{1} < a_{i}$ for all $i>1$. It remains to be noticed that if $\{a_{i}\}_{i=1}^{\infty}$ satisfies the desired condition, then we can delete the first few terms of the sequence without any problem, so the above argument also shows that $a_{2} < a_{i}$ for all $i>2$ and so on, $a_{1} < a_{2} < a_{3} < \cdots$, hence the sequence is indeed strictly increasing.

Structure claim. There exist integers $0 < m_{1} < m_{2} < \dots < m_{k}$ such that $P(x) = (x+m_{1})(x+m_{2})\cdots (x+m_{k})$.

Proof: Let $S = \sum\limits_{i=0}^{k-2} c_{i}$. Call a positive integer $n$ big if $n>S$. For all big integers, we have that $P(n) < n^{k} + (c_{k-1}+1)n^{k-1}$ as
\[P(n) = n^{k} + c_{k-1}n^{k-1} + \sum\limits_{i=0}^{k-2} c_{i}n^{i} \leq n^{k} + c_{k-1}n^{k-1} + n^{k-2}\sum\limits_{i=0}^{k-2} c_{i} < n^{k} + (c_{k-1}+1)n^{k-1}\]As the sequence is strictly increasing, all but finitely many of the $a_{i}$ are not big. Denote $b_{i,j} = a_{i} - a_{j} > 0$ for $i>j$. For big $a_{i}$, we have that
\[a_{i}^{k} + (c_{k-1}+1)a_{i}^{k-1} > P(a_{i}) = \prod\limits_{j=1}^{k} (a_{i}+b_{i+j, i}) > a_{i}^{k} + b_{i+j, i}a_{i}^{k-1}\]For any $1\leq j\leq k$. Thus $b_{i+j, i} \leq c_{k-1}$, so the differences $a_{i+1} - a_{i}$ are bounded by a constant for big $a_{i}$. Therefore the $k$-tuple $(b_{i+1, i}, b_{i+2, i}, \cdots, b_{i+k, i})$ can take on finitely many (at most $c_{k-1}^{k}$) values, so by the PHP there exists a tuple $(e_{1}, e_{2}, \cdots, e_{k})$ such that
\[P(a_{i}) = (a_{i} + e_{1})(a_{i} + e_{2}) \cdots (a_{i} + e_{k})\]holds for infinitely many positive integers $i$. This forces the polynomial $P(x) - \prod\limits_{i=1}^{k} (x+e_{i})$ to have infinitely many distinct real roots, hence must be the constant zero and the claim is proved as clearly $e_{1} < e_{2} < \cdots < e_{k}$ because the sequence $\{a_{i}\}$ is strictly increasing.

Finish. We first show that $m_{i+1} - m_{i}$ is constant and then that $a_{i+1} - a_{i}$ is constant.

Proof: We work with sufficiently large $a_{i}$. Notice that:
\[a_{n}^{k-1} < a_{n+2}a_{n+3}\cdots a_{n+k} \leq \gcd(P(a_{n}), P(a_{n+1})) \leq \prod\limits_{i=1}^{k} \gcd(a_{n}+m_{i}, P(a_{n+1}) ) \leq \prod\limits_{i=1}^{k} \prod\limits_{j=1}^{k} \gcd(a_{n}+m_{i}, a_{n+1}+m_{j})\]Consider a $k \times k$ table with entiries $\gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ in the cell $(i, j)$. For a fixed $i$ consider the quantity $\gcd(a_{n}+m_{i}, a_{n+1}+m_{j})$ ranging over all $j$. Notice that since $n$ is big, we have that:
\[a_{n+1}+m_{j}-a_{n}-m_{i} = m_{j} + b_{n+1, n} - m_{i} \leq 2c_{k-1}-1\]hence if $a_{n}+m_{i} \neq a_{n+1}+m_{j}$, their gcd is bounded from above by a constant. This impies that there's at most one entry $a_{n}+m_{i} < 2a_{n}$ (because $n$ is sufficiently large and $b_{n+i, n}$ is bounded) in the $i$-th row and all other entries must be at most some constant $C = 2c_{k-1}-1$. However, notice that for any $j$ we have:
\[a_{n}+b_{n+1, n} = a_{n+1} < a_{n+1} + m_{j}\]therefore the product of the entries in the first row is bounded by $C^{k}$. Now, for the remaining $k-1$ rows, if we assume that for some $i$ there doesn't exist a $j$ such that $a_{n}+m_{i} = a_{n+1} + m_{j}$, then the product of all entries is bounded from above by
\[C^{2k}\cdot 2^{k-2} \cdot a_{n}^{k-2} < a_{n}^{k-1}\]for sufficiently large $n$ which is a contradiction with the previously established inequality. Hence for every $i>1$ there exists a $j$ such that $a_{n}+m_{i} = a_{n+1}+m_{j}$. Clearly $j = k$ is too big to satisfy such an equality for any $i\leq k$, but also
\[m_{2} < m_{3} < \cdots < m_{k}\]\[m_{1} < m_{2} < \cdots < m_{k-1}\]hence we must have $a_{n} + m_{i} = a_{n+1} + m_{i-1}$. This shows that
\[0 = (a_{n} + m_{i}) - (a_{n+1} + m_{i-1}) = (a_{n}-a_{n+1}) - (m_{i-1}-m_{i})\]proving that $m_{i} - m_{i-1}$ is constant, say $m_{i} - m_{i-1} = L$ and furthermore, for sufficiently large $n$ we have that $a_{n+1}-a_{n} = L$, hence the sequence is eventually an arithmetic progression. Having that in mind, assume that $\{a_{n}\}_{n\geq N}$ is an arithmetic progression. Then
\[P(a_{N-1}) = a_{N}a_{N+1}\cdots a_{N+k} = \prod\limits_{i=1}^{k} (a_{N}+L(i-1)) = P(a_{N}-L)\]which implies that $a_{N-1} = a_{N} -L$ as all the coefficients of $P$ are nonnegative, so if $a<b$, then $P(a) < P(b)$. Inducting downward, in the same manner, shows that every element of the sequence must be part of this increasing arithmetic progression. We showed that these sequences work, so the problem is solved.
Remarks
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
GrantStar
821 posts
#46 • 2 Y
Y by PRMOisTheHardestExam, cubres
ridiculous (shows my alg skill issue, took like >4 hours not including customizing text editor colors so my eyes weren't murdered every time i tried to write this up)
Attachments:
2022 IMO3.pdf (150kb)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ABCDE
1963 posts
#47 • 4 Y
Y by navi_09220114, khina, v_Enhance, cubres
It would be interesting to relax some of the conditions in this problem, but it seems like pretty much all of them are necessary to make the problem tractable.
Th3Numb3rThr33 wrote:
My solution is the same as everyone else’s. Here is a solution path by observing the strength of the conditions in the problem statement, at least for $k=2$.
  • The sequence $a$, $b$, $c$, $a$, $b$, $c$, $a$, $\ldots$ works if we let $P(x) = x^2 -(a+b+c)x+(ab+bc+ca)$, so we must use the fact that all coefficients of $ P$ are nonnegative. This suggests that $P$ monotonically increasing is important (which we can use to show $a_i$ nondecreasing).
  • The sequence $1$, $2$, $4$, $8$, $\ldots$ works if we let $P(x) = 8x^2$, so we must use the fact that $P$ is monic. This suggests that something like $x^{-k+1}P(x) - x$ is bounded is important (which we can use to show $a_{i+1}-a_i$ bounded).
Then the finish is by the same Pigeonhole argument on “constellations” as everyone else.

Adding onto the list of pathological examples, even if we only allow $a_i$ to be arbitrary integers rather than nonnegative and keep all other conditions, we suddenly obtain uncountably many solutions for $k=2m$ even: given any positive integers $r_1,\ldots,r_{2m}$, we may arbitrarily concatenate $0,-r_{\pi_1},\ldots,-r_{\pi_{2m}}$ for arbitrary permutations $\pi$ of $1,\ldots,2m$, and this sequence will work for the polynomial $P(x)=(x+r_1)\cdots(x+r_{2m})$. Similarly, for any positive integers $r_1,\ldots,r_{k-1}$, any sequence consisting of elements of $\{0,-r_1,\ldots,-r_{k-1}\}$ with no consecutive block of nonzero integers of length $k$ will work for the polynomial $P(x)=x(x+r_1)\cdots(x+r_{k-1})$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6877 posts
#48 • 8 Y
Y by GrantStar, aidan0626, megarnie, PRMOisTheHardestExam, Rounak_iitr, math90, Sedro, cubres
Solution from Twitch Solves ISL:

The answer is $a_n$ being an arithmetic progression. Indeed, if $a_n = d(n-1) + a_1$ for $d \ge 0$ and $n \ge 1$, then \[ a_{n+1} a_{n+2} \dots a_{n+k} = (a_n+d)(a_n+2d)\dots(a_n+kd) \]so we can just take $P(x) = (x+d)(x+2d) \dots (x+kd)$.
The converse direction takes a few parts.
Claim: Either $a_1 < a_2 < \cdots$ or the sequence is constant.
Proof. Note that \begin{align*} P(a_{n-1}) &= a_{n}a_{n+1}\cdots a_{n+k-1} \\ P(a_n) &= a_{n+1}a_{n+2}\cdots a_{n+k} \\ \implies a_{n+k} &= \frac{P(a_n)}{P(a_{n-1})} \cdot a_n. \end{align*}Now the polynomial $P$ is strictly increasing over ${\mathbb N}$.
So assume for contradiction there's an index $n$ such that $a_n < a_{n-1}$. Then in fact the above equation shows $a_{n+k} < a_n < a_{n-1}$. Then there's an index $\ell \in [n+1,n+k]$ such that $a_\ell < a_{\ell-1}$, and also $a_\ell < a_n$. Continuing in this way, we can an infinite descending subsequence of $(a_n)$, but that's impossible because we assumed integers.
Hence we have $a_1 \le a_2 \le \cdots$. Now similarly, if $a_n = a_{n-1}$ for any index $n$, then $a_{n+k} = a_n$, ergo $a_{n-1} = a_n = a_{n+1} = \dots = a_{n+k}$. So the sequence is eventually constant, and then by downwards induction, it is fully constant. $\blacksquare$

Claim: There exists a constant $C$ (depending only $P$, $k$) such that We have $a_{n+1} \leq a_n + C$.
Proof. Let $C$ be a constant such that $P(x) < x^k + Cx^{k-1}$ for all $x \in {\mathbb N}$ (for example $C = c_0 + c_1 + \dots + c_{k-1} + 1$ works). We have \begin{align*} a_{n+k} &= \frac{P(a_n)}{a_{n+1} a_{n+2} \dots a_{n+k-1}} \\ &< \frac{P(a_n)}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\ &< \frac{a_n^k + C \cdot a_n^{k-1}}{(a_n+1)(a_n+2)\dots(a_n+k-1)} \\ &< a_n + C + 1. \end{align*}$\blacksquare$
Assume henceforth $a_n$ is nonconstant, and hence unbounded. For each index $n$ and term $a_n$ in the sequence, consider the associated differences $d_1 = a_{n+1} - a_n$, $d_2 = a_{n+2} - a_{n+1}$, \dots, $d_k = a_{n+k}-a_{n+k-1}$, which we denote by \[ \Delta(n) \coloneqq (d_1, \dots, d_k).\]This $\Delta$ can only take up to $C^k$ different values. So in particular, some tuple $(d_1, \dots, d_n)$ must appear infinitely often as $\Delta(n)$; for that tuple, we obtain \[ P(a_N) = (a_N+d_1)(a_N+d_1+d_2) \dots (a_N+d_1+\dots+d_k) \]for infinitely many $N$. But because of that, we actually must have \[ P(X) = (X+d_1)(X+d_1+d_2) \dots (X+d_1+\dots+d_k). \]However, this also means that exactly one output to $\Delta$ occurs infinitely often (because that output is determined by $P$). Consequently, it follows that $\Delta$ is eventually constant. For this to happen, $a_n$ must eventually coincide with an arithmetic progression of some common difference $d$, and $P(X) = (X+d)(X+2d) \dots (X+kd)$. Finally, this implies by downwards induction that $a_n$ is an arithmetic progression on all inputs.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
198 posts
#49 • 3 Y
Y by Iveela, MS_asdfgzxcvb, cubres
Answer: Any arithmetic progression satisfies the problem condition.

Firstly, let $(a_n)_{n\ge 1}$ be an arithmetic progression with difference $d$. Then taking $P(x) = (x+d)(x+2d)\cdots (x+dk)$ works.

Now we'll prove that the sequence $(a_n)_{n\ge 1}$ is an arithmetic progression. Consider the following claim:

Claim: $a_n \le a_{n+1}$ for all $n \ge 1$.

Proof. Assume the contrary, $a_n > a_{n+1}$ for some $n$. Then note that $P$ increases on $[0, \infty)$, hence $P(a_n) > P(a_{n+1})$, which means $a_{n+1}a_{n+2}\cdots a_{n+k} > a_{n+2}a_{n+3}\cdots a_{n+k+1}$, or equivalently $a_{n+1} > a_{n+k+1}$. Hence there exists $n_1$ such that $a_{n_1} > a_{n_1+1} \le a_{n_1+2} \le \dots \le a_{n+k+1}$. Thus $a_{n_1+1} < a_{n+k+1} < a_{n+1} < a_{n}$, so replacing $n \to n_1$ and repeating the same argument on $n_1$, we get there exists $n_2$ such that $a_{n_2} > a_{n_2+1}$ and $a_{n_2+1} < a_{n_1+1} < a_{n+1}$. Thus repeating same argument over and over, we get there exists an increasing sequence $(n_k)_{k\ge 0}$ such that $a_{n_i+1} > a_{n_{i+1}+1}$ for all $i \ge 0$, so $a_{n_0+1} > a_{n_1+1} > a_{n_2+1} > \dots >$, contradicting the fact that the sequence $(a_n)_{n\ge 1}$ takes positive integer values. $\blacksquare$

Thus by claim, $a_{n+i} - a_n \ge 0$ for all $1 \le i \le k$.

Claim: $a_{n+k} - a_n$ is bounded above.

Proof. Suppose $a_{n+k} - a_n$ takes arbitrarily large values. Since $\deg(P) = k$, so there exists $c$ such that $P(x) < (x+c)^k$ for all $x > 0$. Let $N$ be a sufficiently large integer. Then there exists $n$ such that $a_{n+k} - a_n \ge N$. So $a_n^k + N \cdot a_n^{k-1} = a_n^{k-1}(a_n+N) \le a_{n+1}a_{n+2}\cdots a_{n+k} = P(a_n) < (a_n+c)^k$, contradicting $N$ is sufficiently large. $\blacksquare$

Let $S_n$ be $k-$tuplet of integers $(a_{n+1} - a_n, a_{n+2} - a_n, \dots, a_{n+k} - a_n)$. We say that tuplets $(a_1, a_2, \dots, a_k)$ and $(b_1, b_2, \dots, b_k)$ are equal if and only if $a_i = b_i$ for $1 \le i \le k$. Then by claim, all integers in any tuplets doesn't exceed a certain integer, so by infinite pigeonhole principle, there exists an increasing sequence $(i_n)_{n\ge 1}$ such that $S_{i_1} = S_{i_2} = \dots$. Let $d_j = a_{i_1 + j} - a_{i_1}$ for $1 \le j \le k$ and let $Q(x) = (x+d_1)(x+d_2)\cdots (x+d_k)$. Then we have $Q(a_{i_n}) = P(a_{i_n})$ for all $n \ge 1$, which means $a_{i_n}$ is root of $P(x) - Q(x)$, which means $P(x) = Q(x)$ or the sequence $(a_n)_{n\ge 1}$ is eventually constant. If the sequence $(a_n)_{n\ge 1}$ is eventually constant, then $P(x) = x^k$ and backward induction shows that $(a_n)_{n\ge 1}$ is constant sequence. Thus we can assume $(a_n)_{n\ge 1}$ is nonconstant sequence, and thus we get $P(x) = Q(x) = (x+d_1)(x+d_2)\cdots (x+d_k)$. If there exists an increasing sequence $(j_n)_{n\ge 1}$ such that $S_{j_1} = S_{j_2} = \dots$ and $S_{j_1} \neq S_{i_1}$, then we get $\prod_{a \in S_{i_1}}(x+a) = P(x) = \prod_{a \in S_{j_1}}(x+a)$, which is an evident contradiction. Hence for sufficiently large integer $n$, we get $S_n = S_{i_1}$. Therefore $a_{n+i} - a_n = d_i$ for all sufficiently large integer $n$, which means $d_i + d_j = d_{i+j}$ for all $1 \le i, j \le k$ satisfying $i + j \le k$, which shows that $d_i = i \cdot d$ for some $d \ge 0$. Thus the sequence $(a_n)_{n\ge 1}$ eventually becomes an arithmetic progression. Now backward induction shows that $(a_n)_{n\ge 1}$ is an arithmetic progression, as required. $\blacksquare$
This post has been edited 1 time. Last edited by thdnder, Jun 16, 2024, 6:19 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pi271828
3369 posts
#50 • 2 Y
Y by Rounak_iitr, cubres
We will prove that the only sequences that work are arithmetic sequences.

Claim: $a_n$ is non-decreasing

Let $a_i$ be a minimum of the sequence. If $a_1$ is a unique minimum, then "delete" this term, shift indices down by $1$, and repeat the process. If the process repeats infinitely than obviously $a_n$ is non-decreasing. If not however, then we proceed with the following. We have $$a_iP(a_i) = a_{i+k}P(a_{i-1})$$If $a_{i-1} \neq a_i$ then we simply have $a_i > a_{i+k}$ which is a clear contradiction. Therefore $a_{i-1} = a_i$, and even further all $a_j = a_i$ for $j < i$. Note that $a_i = a_{i+k}$ and we can repeat the process for $a_{i+k}$ as it is a minimum. From this we can "induct" to prove that $a_n$ must be constant which clearly means it is non decreasing.

We now let $b_n \coloneq a_{n+1} - a_n$ and prove the following claim. Note that $b_n$ is nonnegative for all $n$.

Claim: $b_n$ is bounded above

Assume FTSOC that $b_n$ is not bounded and achieves arbitrarily large values. Observe that \begin{align*} P(a_n) = \prod_{i=1}^{k} a_{n+i} \\ = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right) > (a_n+b_n)^k\end{align*}
Now since $b_n$ can achieve arbitrarily large values, we can select the index $n$ where $b_n > \frac{c_i}{{k \choose i}}$ for all $i$ and we have a clear contradiction.

Now there are obviously a finite amount of possibilities of $k$-tuples $\left(b_n, b_{n+1}, \dots, b_{n+k-1}\right)$ where $n$ varies, but obviously an infinite amount of tuples that exist, so by PHP there exists a tuple that appears infinitely many times. This implies that $$P(a_n) = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right)$$for infinitely many $a_n$ so we have $$P(x) = \prod_{i=0}^{k} \left(a_n + \sum_{j=0}^{i} b_{n+j}\right)$$as a polynomial identity. Now, this immediately implies that all other $k$-tuples appear only a finite amount of times, which also implies that eventually this special $k$-tuple should be the only one that appears. This is only possible if $b_n = b_{n+1} = b_{n+2} = \dots = b_{n+k-1}$

We now finish by inducting down. FTSOC assume the index $i$ is the minimum value where $a_i$ "starts" behaving like an arithmetic sequence (Ex. $a_k = a_{k-1} + d$ for all $k \ge i+1$). Now we have $$P(a_{i-1}) = \prod_{j = 1}^{k} \left(a_{i-1} + j \cdot d\right) = \prod_{j = 0}^{k-1} \left(a_{i} + j \cdot d\right)$$which directly implies $a_{i-1} + d = a_i$, so we can just induct all the way down.
This post has been edited 1 time. Last edited by pi271828, Mar 29, 2024, 1:36 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Pyramix
419 posts
#51 • 1 Y
Y by cubres
We prove that only arithmetic sequences work.

Suppose $a_1,a_2,\ldots$ is a sequence that works.

Claim 1: $P(x)$ is strictly increasing and injective polynomial for $x>0$.
Proof. Take $a,b$ such that $a>b>0$. Since $c_i$ are non-negative numbers, we have $c_ia^i \leq c_ib^i$ for each $1\leq i\leq k$, and the inequality is strict for $i=k$. Adding, we get that $P(a) > P(b)$, as desired. $\blacksquare$

Since the polynomial is strictly increasing, it is naturally injective as well.

Claim 2: $a_{n+1}> a_n$ for each $n\in\mathbb{N}$, or $a_n\equiv C'$ for each $n\in\mathbb{N}$.
Proof. Suppose $a_{n+1} < a_n$. Then, \[P(a_{n+1}) < P(a_{n})\Longrightarrow \frac{a_{n+k+1}}{a_{n+1}}\cdot P(a_{n}) < P(a_{n})\Longrightarrow a_{n+k+1} < a_{n+1}\]Consider the minimum from $\{a_n,a_{n+1},\ldots,a_{n+k-1}\}$. If $a_{n+t}$ is the minimum with $t\geq 1$, then $a_{n+t+k} < a_{n+t}$, which means minimum of $\{a_{n+k},a_{n+k+1},\ldots,a_{n+2k-1}\}$ is at most $a_{n+t}-1$. Continuing, we get contradiction, unless $a_n=a_{n+1}=\cdots=a_{n+t}$. Shifting $n$ front and back, we get that all terms are equal to some constant, $C'$ (which is the constant A.P.). $\blacksquare$

Claim 3: $a_{n+1}-a_{n}<C$, for some constant $C$.
Proof. Take $C$ such that for each $0\leq i < k$, we have that $\binom{k}{i}C^{k-i} > c_i$. Then, $(x+C)^k > P(x)$ for each $x>0$. Finally, note
\[(a_n+C)^k=P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}\geq a_{n+1}^k\Longrightarrow a_n+C\geq a_{n+1}\Longrightarrow a_{n+1}-a_n\leq C,\]as claimed. $\blacksquare$

Claim 4: $a_{n+1}-a_{n}$ is constant.
Proof. If $a_{n}=a_{n+1}$ for any $n$ then the sequence is constant, from Claim 2.
Assume that the sequence is not constant. Then, from Claim 2, it is strictly increasing, which means that it is unbounded above. So, it achieves infinitely many distinct positive integer values.
Note that $\{a_{n+1}-a_{n},a_{n+2}-a_{n+1},\ldots,a_{n+k+1}-a_{n+k}\}\subseteq\{1,2,\ldots,C\}$. Since there are only finitely many subsets (at most $2^C-1$) possible, at least one subset appears infinitely many times for sufficiently many $n$. Suppose that ordered tuple is \[(a_{n+1}-a_{n},a_{n+2}-a_{n+1},\ldots,a_{n+k+1}-a_{n+k})=(b_1,b_2,\ldots,b_{k+1}).\]This means
\[P(x)=\left(x+b_1\right)\left(x+b_1+b_2\right)\cdots\left(x+\sum_{i=1}^{k}b_i\right)\]for infintely many $x=a_n$. Since $\deg P=k$ is finite, it means that the above equation is an identity.
Similarly,
\[P(x)=\left(x+b_2\right)\left(x+b_2+b_3\right)\cdots\left(x+\sum_{i=2}^{k+1}b_i\right)\]is an identity.
Comparing, we get that $b_1=b_2$ by noticing that $P\left(-b_1\right)=P\left(-b_2\right)=0$. Then, substituting $x+b_2$ as $x$, we obtain $b_1=b_3$ and so on. Eventually, we get $b_1=b_2=\cdots=b_{k+1}$. Hence, $a_{n+1}-a_{n}$ is constant, which means it is an increasing arithmetic sequences. Combining this with the fact that constant sequences work as well, we have that arithmetic sequences.

We now provide the construction for arithmetic sequences.

Suppose $a_n=a_1+(n-1)d$ for each $n\in\mathbb{N}$. Then, the polynomial
\[P(x)=(x+d)(x+2d)\cdots(x+kd)\]works, as $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ for each $n\in\mathbb{N}$.

The proof is complete. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Qzxell
1 post
#52 • 1 Y
Y by cubres
799786 wrote:
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$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8860 posts
#53 • 1 Y
Y by cubres
The answer is constant and increasing arithmetic sequences only, which work by setting $P(x) = (x+d)(x+2d) \cdots (x+kd)$.

Claim. The sequence $\{a_n\}$ is nondecreasing.

Proof. Suppose that there is an index $i > N$ with $a_i > a_{i+1}$. Notice that if $a > b > 0$ then $P(a) > P(b)$ as it has nonnegative coefficients. Thus, for any index $j$, with $a_j > a_{j+1}$, we have\[a_{j+1}a_{j+2} \cdots a_{j+k} = P(a_j) > P(a_{j+1}) = a_{j+2}a_{j+3} \cdots a_{j+k+1}\]so in particular $a_j > a_{j+1} > a_{j+k+1}$.

Then, for every index $i$, either $a_i \geq a_{i-1}$ or $a_{i-1} < a_i$, implying $a_i > a_{i+k}$ by the previous argument. Thus, there is a subsequence $a_{n_j}$ with $n_{j+1} \in \{n_j + k, n_j - 1\}$ such that $a_{n_{j+1}} \leq a_{n_j}$ for each $j$.

Claim. $n_j > i$ for all $j > 1$.

Proof. Note that $n_1 = i$ and $n_2 = i+k+1$. Let $n_r$ be the first index less than $i$. Then $n_{r-1} = n_r + 1 = i$, otherwise we contradict minimality. But $a_i = a_{n_{r-1}} \leq a_{n_2} < a_i$, contradiction. $\blacksquare$

In particular, I claim that there are infinitely many indices $j$ with $a_{n_{j+1}} < a_{n_j}$. Suppose that for all $j > M$ equality holds; then we must have $n_{j+1} = n_j - 1$ for all these $j$ by assumption. Then for $A = n_M$, notice that $n_{M+A-i} = A - (A-i) = i$, contradiction.

Hence we have constructed an infinite sequence of strictly decreasing positive integers $a_{n_j}$, which is a contradiction. $\blacksquare$

The rest of the proof goes rather quickly. By the previous claim, we will pick $a_n > M$ very large, with $M$ to be determined. Furthermore, let $b_i = a_i - a_{i-1} \geq 0$ for each $i$.

Then, the given condition applied on $a_n$ yields that the polynomial
\[Q(x) = P(x) - (x+b_{n+1})(x+b_{n+1}+b_{n+2}) \cdots (x+b_{n+1}+b_{n+2} + \cdots + b_{n+k})\]has a root at $a_n > 0$.

Claim. $Q \equiv 0$.

Proof. Suppose otherwise. Then there is an index $j$ with $c_{k-j} > S_j$, where $S_j$ is the $j$th symmetric sum of $b_{n+1}, b_{n+1}+b_{n+2}, \dots, b_{n+1}+b_{n+2}+\cdots+b_{n+k}$. In particular, as all the $b_i$ are nonnegative integers, there are only finitely many possible values of the $k$-tuple $(b_{n+1}, b_{n+2}, \dots, b_{n+k})$ as $c_{k-j}$ is a constant.

Let $i$ be the smallest index for which $c_{k-i} \neq S_i$ (the coefficients are not equal), and let $M_j = \sup |S_j - c_{k-j}|$ across all $k$-tuples $(d_1, d_2, \dots, d_k)$ (note that $M_j$ only depends on the value of $c_{k-j}$) for each $j > i$. It follows that
\begin{align*}
|Q(a_n) - P(a_n)| &= |c_{k-i}a_n^{k-i} - S_i a_n^{k-i} + c_{k-i-1}a_n^{k-i-1} - S_{i+1} a_n^{k-i-1} + \cdots + c_0 - S_k| \\
&\geq |c_{k-i}-S_i||a_n^{k-i}| - \sum_{j=i+1}^k |a_n^{k-j}| |S_j - c_{k-j}| \\
&\geq a_n^{k-i} - \sum_{j=i+1}^k M_j a_n^{k-j} \\
&\geq a_n^{k-i} - (k-i) \sup_j M_j a_n^{k-i-1}.
\end{align*}By taking $a_n > M = (k-i) \sup_j M_j$ (which does not depend on $n$), we have a contradiction, as needed. $\blacksquare$

Hence the roots of $P$ are precisely $-b_{n+1}, -b_{n+1}-b_{n+2}, \cdots$. In particular, repeating the argument for $a_{n+1} > a_n$, we have
\[\{b_{n+1}, b_{n+1}+b_{n+2}, \dots, b_{n+1}+\cdots+b_{n+k}\} = \{b_{n+2}, b_{n+2} + b_{n+3}, \dots, b_{n+2} + \cdots + b_{n+k+1}\}\]as all the elements in each set are distinct. But $b_{n+2}$ is less than all of the first element of the first set, so $b_{n+2} = b_{n+1}$. Repeating this argument, we see that $b_n = d$ is constant for all $n > N$.

To finish the problem, we just induct down. Given that $b_i = d$ for all $i \geq \ell+2$, we have
\[(a_\ell + d)(a_\ell + 2d) \cdots (a_\ell + kd) = P(a_\ell) = (a_\ell + b_{\ell+1})(a_\ell + b_{\ell+1} + d) \cdots (a_\ell + b_{\ell + 1} + (k-1)d).\]Considering this as a polynomial $R$ in $x = b_{\ell + 1} - d$, we have $P(x) = P(0)$ and $P$ is strictly increasing on $(-a_\ell - d, \infty)$, so $x = 0$ and $b_{\ell + 1} = d$, as needed. This completes the induction and shows that $\{a_n\}$ is an arithmetic sequence, as needed.
This post has been edited 1 time. Last edited by HamstPan38825, Jun 23, 2024, 6:13 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
axolotlx7
133 posts
#54 • 2 Y
Y by LLL2019, cubres
The answer is all arithmetic sequences with common difference $d \geq 0$. The corresponding polynomial is $P(x)=(x+d)(x+2d) \dots (x+kd)$.

Claim 1. $a_n \geq a_{n-1}$ for all $n$.
Proof. Suppose FTSOC that $a_n < a_{n-1}$ for some $n$. Then $a_{n+1}a_{n+2} \dots a_{n+k} = P(a_n) < P(a_{n-1}) = a_na_{n+1} \dots a_{n+k-1}$ implies $a_{n+k} < a_n$, so consider the smallest index $n' \in [n+1, n+k]$ satisfying $a_{n'} < a_n$. Then $a_{n'} < a_{n'-1}$ and we can repeat this process to generate a decreasing subsequence of positive integers, contradiction. $\square$

Claim 2. $(a_n)$ is either constant or strictly increasing.
Proof. Suppose $a_n = a_{n-1}$. Then $a_{n+1}a_{n+2} \dots a_{n+k} = P(a_n) = P(a_{n-1}) = a_na_{n+1} \dots a_{n+k-1}$ implies $a_{n+k} = a_n$, so by Claim 1 we have $a_n = a_{n+1} = \dots = a_{n+k}$. The given condition implies $P(a_n) \geq a_n^k$, and here equality holds which forces $P(x) = x^k$. We can work backwards to obtain that $(a_n)$ is constant. $\square$

Henceforth suppose $(a_n)$ is strictly increasing.
Claim 3. $d_n = a_{n+1} - a_n$ is bounded.
Proof. Suppose not. Then consider
\[ a_n^k+c_{k-1}a_n^{k-1}+\dots + c_1a_n+c_0 = P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k} > a_{n+1}^k = (a_n + d_n)^k . \]However, for $d_n$ sufficiently large, each term in the expansion of the RHS will be larger than the corresponding term in the LHS, contradiction. $\square$

Let $S_n = (a_{n+1}-a_n, a_{n+2}-a_n, \dots, a_{n+k}-a_n)$. As each element is bounded by applying Claim 3, there are only finitely possible values for $S_n$. Hence by infinite Pigeonhole there exists $S = (z_1, z_2, \dots, z_k)$ such that $S_n = S$ infinitely often.

Claim 4. $P(x) = (x+z_1)(x+z_2) \dots (x+z_k)$.
Proof. As $P(x)-(x+z_1)(x+z_2) \dots (x+z_k)$ is a polynomial and equals zero infinitely often, it must be identically zero. $\square$

Claim 5. $S_n = S$ for all sufficiently large $n$.
Proof. Let $S_n = (w_1, w_2, \dots, w_k)$. Then
\[ (a_n + z_1)(a_n + z_2) \dots (a_n + z_k) = P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k} = (a_n + w_1)(a_n + w_2) \dots (a_n + w_k) \]and as the $w_i$'s are bounded, we can take $a_n > \max \{ w_1, \dots, w_k, z_1, \dots, z_k \}$. Then if one expands each side, they are valid representations of the same number in base $a_n$, so each corresponding term must be equal which implies $(x + z_1)(x + z_2) \dots (x + z_k) \equiv (x + w_1)(x + w_2) \dots (x + w_k)$. As $w_1 < \dots < w_k$ and $z_1 < \dots < z_k$, we conclude that $S_n = S$ as desired. $\square$

In particular, for sufficiently large $n$ we have $S_{n+1} = S_n$, so $d_{n+1} = d_n$, so $d_n$ eventually equals some constant $d$. By Claim 4 we have $P(x)=(x+d)(x+2d) \dots (x+kd)$ and may work backwards to conclude that $d_n = d$ for all $n$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
N3bula
270 posts
#55 • 1 Y
Y by cubres
Suppose the minimum of the sequence $a_n$ has the property $a_{n-1}>a_n$ for $n\neq 1$, we get that $a_{n+k}P(a_{n-1})=a_nP(a_n)<a_nP(a_{n-1})$ which is a contradicition
as we know a minimum must exist. Thus $a_n$ is non strictly increasing. Note that there exists a value $y$ such that $(x+y)^k\geq P(x)$ for all $x$. Thus we get
that $a_{n}+y\geq a_{n+1}$ from the non decreasing. This suffices to prove that it is bounded, from pigeon hole plus FTOA we get that is must be an arithmetic progression.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathandski
757 posts
#56 • 1 Y
Y by cubres
Subjective Rating (MOHs)
Please contact westskigamer@gmail.com if there is an error with any of my solution for cash bounties by 3/18/2025.

Note on above: The beef is this solution is the same as Evan's so idt it's likely there'll be an error here
Attachments:
This post has been edited 1 time. Last edited by Mathandski, Jan 16, 2025, 6:58 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pie854
243 posts
#57 • 1 Y
Y by cubres
Really nice problem but I could only do it for $k=2$ rip

The answer is $a_i=c+(i-1)d$ for every $i\geq 1$ where $c \in \mathbf N$, $d \in \mathbf Z_{\geq 0}$. This sequence clearly works (take $p=3d$, $q=2d^2$). Now we will prove that this is the only sequence that works.

Claim: If $\{a_n\}$ is not constant then $a_{n+1}>a_n$ for every $n\geq 1$.

Proof. Suppose that $a_2<a_1$. Note that $$a_1a_3>a_2a_3=a_1^2+pa_1+q>a_1^2 \ \Rightarrow \ a_3>a_1.$$Now suppose we have shown that $a_{2k+1}>a_{2k-1}>\dots>a_3>a_1>a_2>\dots>a_{2k-2}>a_{2k}$ for some $k\geq 1$. Then, \begin{align*} a_{2k+1}a_{2k+2}=a_{2k}^2+pa_{2k}+q<a_{2k-1}^2+pa_{2k-1}+q=a_{2k}a_{2k+1} & \ \Rightarrow \ a_{2k+2}<a_{2k} \\ a_{2k+1}^2\leq a_{2k+1}^2+pa_{2k+1}+q = a_{2k+2}a_{2k+3}<a_{2k+1}a_{2k+3} & \ \Rightarrow \ a_{2k+1}<a_{2k+3}. \end{align*}Thus, $$a_{2k+3}>a_{2k+1}>a_{2k-1}>\dots>a_3>a_1>a_2>\dots>a_{2k-2}>a_{2k}>a_{2k+2}.$$By induction it follows that $\{a_{2n}\}$ is a strictly decreasing sequence. However this is a contradiction since $\{a_{2n}\}$ is a sequence of positive integers and as such, it cannot be strictly decreasing. Hence we must have $a_2\geq a_1$. The same argument proves that $a_{i+1}\geq a_i$ for every $i\geq 1$.

Suppose that $a_2=a_1$. Then, $a_3=\frac{a_1^2+pa_1+q}{a_1}$ and $$a_4=\frac{a_2^2+pa_2+q}{a_3}=\frac{a_1^2+pa_1+q}{\frac{a_1^2+pa_1+q}{a_1}}=a_1.$$But we have proved already that $a_4\geq a_3$ i.e. $$a_1\geq \frac{a_1^2+pa_1+q}{a_1} \ \Rightarrow \ 0\geq pa_1+q \ \Rightarrow \ p=q=0.$$Thus, $a_i^2=a_{i+1}a_{i+2}$ for every $i\geq 1$. From this we derive that $a_i$ must be constant. The claim follows. ////

Let us define another sequence of positive integers $\{t_n\}_{n\geq 2}$ by $a_{n+1}=a_n+t_{n+1}$. So we have \begin{align*} a_i^2+pa_i+q & =(a_i+t_{i+1})(a_i+t_{i+1}+t_{i+2}) \\ pa_i+q & =a_i(2t_{i+1}+t_{i+2})+t_{i+1}(t_{i+1}+t_{i+2}) \qquad (1)\end{align*}
Let $l$ be such that $a_l>q$. Note that, from $(1)$, we have $$q>a_l(2t_{l+1}+t_{l+2}-p)>q(2t_{l+1}+t_{l+2}-p) \ \Rightarrow \ 2t_{l+1}+t_{l+2}-p\leq 0.$$Thus we must have $$2t_{n+1}+t_{n+2}\leq p\qquad (2)$$for every $n\geq l$. Let $S$ be the set of all $n\in \mathbf N$ such that if $n\in S$ then $2t_{n+1}+t_{n+2}<p$. Let $p':=\max_{n\in S}(2t_{n+1}+t_{n+2})<p$. Suppose that $S$ has infinitely many elements. For every $n\in S$, \begin{align*} a_n(p-p')\leq a_n(p-2t_{n+1}-t_{n+2})=t_{n+1}(t_{n+1}+t_{n+2})-q \\ \Rightarrow \ a_n\leq \frac{t_{n+1}(t_{n+1}+t_{n+2})-q}{p-p'}\end{align*}Note that $t_{n+1}(t_{n+1}+t_{n+2})$ is bounded (this is quite clear from $(2)$). It follows that $a_n$ is bounded for every $n\in S$, but this is a contradiction since we showed that $\{a_n\}$ is strictly increasing. Thus $S$ must be a finite set. And so there must exist some $m\geq l$ such that $2t_{n+1}+t_{n+2}=p$ for every $n\geq m$ and also from $(1)$, $t_{n+1}(t_{n+1}+t_{n+2})=q$. From these equations it's easy to get that $t_{n+1}$ must be constant for every $n\geq m$.

Let $t_i=t$ for $i\geq m+1$ then we also have $p=3t$, $q=2t^2$. Now the equation in $(1)$ for $i=m-1$ implies that $$3ta_{m-1}+2t^2=a_{m-1}(2t_m+t)+t_m(t_m+t)\iff (t_m-t)(2a_{m-1}+3t_m+t)=0,$$thus $t_m=t$. At this point it is evident by induction that we must have $t_i=t$ for every $i\geq 2$. This completes the proof.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihatemath123
3446 posts
#58 • 1 Y
Y by cubres
Arithmetic sequences clearly work, so we will show they are the only solutions.

Claim: If $a_i$ is not constant, it is strictly increasing.
Proof: Suppose for the sake of contradiction that $a_1 > a_2$ (we can truncate a sequence so that this is true). Then, since $P$ is an increasing function, we have
\[a_2 a_3 \cdots a_{1+k} > a_3 a_4 \cdots a_{2+k} \implies a_2 > a_{2+k},\]so there exists an integer $i$ strictly between $1$ and $2+k$ for which $a_i > a_{i+1}$ and $a_{i+1} < a_2$. Now we can truncate our sequence at $i$ and repeat until we get a contradiction.

Claim: $a_{i+1} - a_i$ is bounded.
Proof: For a sufficiently large constant $C$, we have $(x+C)^k > P(x)$ for all $x$, so $a_{i+1} < a_i + C$.

So by pigeonhole, the function $f(i) = (a_{i+1} - a_i, a_{i+2} - a_i, \dots, a_{i+k} - a_i)$ must map infinitely many integers $i$ to the same $k$-tuple $(r_1, r_2, \dots, r_k)$. In other words, $P(x) = (x-r_1) \cdots (x-r_k)$ for infinitely many $x$, implying that the equality holds for all $x$. So, $f(i)$ is a constant function. Comparing $f(i)$ and $f(i+1)$, it follows that $a_1, a_2, \dots$ is an arithmetic sequence.
This post has been edited 1 time. Last edited by ihatemath123, Feb 22, 2025, 4:38 PM
Z K Y
N Quick Reply
G
H
=
a