Summer is a great time to explore cool problems to keep your skills sharp!  Schedule a class today!

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
Sums of products of entries in a matrix
Stear14   0
a few seconds ago
(a) $\ $Each entry of an $\ 8\times 8\ $ matrix equals either $\ 1\ $ or $\ 2.\ $ Let $\ A\ $ denote the sum of eight products of entries in each row. Also, let $\ B\ $ denote the sum of eight products of entries in each column. Find the maximum possible value of $\ A-B.\ $ In other words, find
$$ {\rm max}\ \left[ \sum_{i=1}^8\ \prod_{j=1}^8\ a_{ij} - 
\sum_{j=1}^8\ \prod_{i=1}^8\ a_{ij} \right]
$$
(b) $\ $Same question, but for a $\ 2025\times 2025\ $ matrix.
0 replies
Stear14
a few seconds ago
0 replies
a father and his son are skating around a circular skating rink
parmenides51   2
N 17 minutes ago by thespacebar1729
Source: Tournament Of Towns Spring 1999 Junior 0 Level p1
A father and his son are skating around a circular skating rink. From time to time, the father overtakes the son. After the son starts skating in the opposite direction, they begin to meet five times more often. What is the ratio of the skating speeds of the father and the son?

(Tairova)
2 replies
parmenides51
May 7, 2020
thespacebar1729
17 minutes ago
Sums of n mod k
EthanWYX2009   1
N 19 minutes ago by Martin.s
Source: 2025 May 谜之竞赛-3
Given $0<\varepsilon <1.$ Show that there exists a constant $c>0,$ such that for all positive integer $n,$
\[\sum_{k\le n^{\varepsilon}}(n\text{ mod } k)>cn^{2\varepsilon}.\]Proposed by Cheng Jiang
1 reply
EthanWYX2009
May 26, 2025
Martin.s
19 minutes ago
Easy P4 combi game with nt flavour
Maths_VC   1
N 3 hours ago by p.lazarov06
Source: Serbia JBMO TST 2025, Problem 4
Two players, Alice and Bob, play the following game, taking turns. In the beginning, the number $1$ is written on the board. A move consists of adding either $1$, $2$ or $3$ to the number written on the board, but only if the chosen number is coprime with the current number (for example, if the current number is $10$, then in a move a player can't choose the number $2$, but he can choose either $1$ or $3$). The player who first writes a perfect square on the board loses. Prove that one of the players has a winning strategy and determine who wins in the game.
1 reply
Maths_VC
May 27, 2025
p.lazarov06
3 hours ago
No more topics!
Quadratic system
juckter   35
N May 10, 2025 by shendrew7
Source: Mexico National Olympiad 2011 Problem 3
Let $n$ be a positive integer. Find all real solutions $(a_1, a_2, \dots, a_n)$ to the system:

\[a_1^2 + a_1 - 1 = a_2\]\[ a_2^2 + a_2 - 1 = a_3\]\[\hspace*{3.3em} \vdots \]\[a_{n}^2 + a_n - 1 = a_1\]
35 replies
juckter
Jun 22, 2014
shendrew7
May 10, 2025
Quadratic system
G H J
Source: Mexico National Olympiad 2011 Problem 3
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
324 posts
#1 • 7 Y
Y by itslumi, samrocksnature, jhu08, Adventure10, Mango247, Gato_combinatorio, ehuseyinyigit
Let $n$ be a positive integer. Find all real solutions $(a_1, a_2, \dots, a_n)$ to the system:

\[a_1^2 + a_1 - 1 = a_2\]\[ a_2^2 + a_2 - 1 = a_3\]\[\hspace*{3.3em} \vdots \]\[a_{n}^2 + a_n - 1 = a_1\]
This post has been edited 1 time. Last edited by juckter, Dec 5, 2016, 2:01 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tensor
433 posts
#2 • 4 Y
Y by aerile, samrocksnature, Adventure10, Mango247
Proof 1:This proof is quite flawed but i think it can be repaired plz give ur suggestions

proof 2
This post has been edited 8 times. Last edited by tensor, Jun 22, 2014, 7:57 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aerile
8 posts
#3 • 5 Y
Y by tensor, samrocksnature, Adventure10, Mango247, BR1F1SZ
tensor wrote:
Suppse in the way of contradiction $\exists k$ such that $a_{k-1}>a_k$
$\implies a_k=a_{k-1}^2+a_{k-1}+1>a_k^2+a_k-1\implies |a_k|<1$
$a_{k-1}>a_k$ does not imply $|a_k|<1$, for example, $a_{k-1}=-1/2 \implies a_k=-5/4$

I think we need to consider f(f(x)) where f(x)=x^2+x-1,
to show $-1<x<0 \implies -1<f(f(x))<x<0$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MexicOMM
292 posts
#4 • 5 Y
Y by tensor, samrocksnature, Adventure10, Mango247, ehuseyinyigit
Hint: sum all the equations.
2 Hint: sum 1 to all equations, and then multiply this ones.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tensor
433 posts
#5 • 3 Y
Y by samrocksnature, Adventure10, Mango247
aerile wrote:
tensor wrote:
Suppse in the way of contradiction $\exists k$ such that $a_{k-1}>a_k$
$\implies a_k=a_{k-1}^2+a_{k-1}+1>a_k^2+a_k-1\implies |a_k|<1$
$a_{k-1}>a_k$ does not imply $|a_k|<1$, for example, $a_{k-1}=-1/2 \implies a_k=-5/4$

I think we need to consider f(f(x)) where f(x)=x^2+x-1,
to show $-1<x<0 \implies -1<f(f(x))<x<0$.

Aerile @... OH REALLY?? but unfortunately ur counterexample doesn't seem to work

$a_{k-1}^2+a_{k-1}-1=\frac 14-\frac 12+1\neq \frac 54=a_k$
This post has been edited 1 time. Last edited by tensor, Jun 22, 2014, 6:45 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aerile
8 posts
#6 • 3 Y
Y by samrocksnature, Adventure10, Mango247
tensor wrote:
$a_{k-1}^2+a_{k-1}-1=\frac 14-\frac 12+1\neq \frac 54=a_k$ :D
You are changing the constant -1 into +1
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tensor
433 posts
#7 • 3 Y
Y by samrocksnature, Adventure10, Mango247
oho noo i should learn how to see my typos thanks friend :wallbash: :wallbash_red:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aerile
8 posts
#8 • 2 Y
Y by samrocksnature, Adventure10
MexicOMM wrote:
Hint: sum all the equations.
2 Hint: sum 1 to all equations, and then multiply this ones.
That's a nice way. I think the Third Hint will be the AM-GM inequality:
$(\frac{a_1^2+a_2^2+...+a_n^2}{n})^n \geq (a_1a_2...a_n)^2$
with equality if and only if $a_1^2=a_2^2=...=a_n^2$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
randomusername
1059 posts
#9 • 7 Y
Y by aerile, abbosjon2002, pavel kozlov, samrocksnature, Adventure10, Mango247, MarioLuigi8972
Let's compile a complete solution.
juckter wrote:
Let $n$ be a positive integer. Find all real solutions $(a_1, a_2, \dots, a_n)$ to the system:

\[a_1^2 + a_1 = a_2 +1\\
  a_2^2 + a_2 = a_3 +1\\
  \hspace*{3.3em} \vdots \\
 a_{n}^2 + a_n = a_1 +1\]

Adding these $n$ equations we get $a_1^2+a_2^2+\dots+a_n^2=n$. (1)
Multiplying these equations we arrive at $\prod_{i=1}^n (a_i^2+a_i)=\prod_{i=1}^n(a_i+1)$, so we get
$(a_1a_2\dots a_n-1)(a_1+1)(a_2+1)\dots (a_n+1)=0$. (2)
Now in (2) we may have $a_i=-1$ for some $i$. Then we get $a_{i+1}=a_i^2+a_i-1=1-1-1=-1$, $a_{i+2}=-1$, and so on. It is easy to see that $a_1=a_2=\dots=a_n=-1$ is in fact a solution of the system.
Next consider the more general case $a_1\dots a_n=1$. Using the AM-GM inequality, we get
$1=\frac{a_1^2+\dots+a_n^2}n\ge \root{n}\of{a_1^2a_2^2\dots a_n^2}=1$,
where equality only holds if $a_1^2=a_2^2=\dots=a_n^2=A$. Put $a=\sqrt A$, then all the $a_i$ are $\pm a$.
The system becomes ($a_{n+1}:=a_1$)
$a_{i+1}-a_i=A-1$, $i=1,2,\dots,n$.
Adding these for $i=1,\dots,n$ gives $n(A-1)=0$, $A=1$, $a=1$. This means $a_1=\dots=a_n=+1$ or $=-1$. Both are solutions.
Therefore there are two solutions:
$a_1=\dots=a_n=1$ and $a_1=\dots=a_n=-1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aerile
8 posts
#10 • 4 Y
Y by tensor, samrocksnature, Adventure10, Mango247
tensor wrote:
Proof 1:This proof is quite flawed but i think it can be repaired plz give ur suggestions
Actually, $a_{k-1}>a_{k}$ implies $a_{k-1}>a_{k-1}^2+a_{k-1}-1$.
Solving this quadric inequality, the thing we have is $-1<a_{k-1}<1$.

$|a_k|<1$ holds if $0<a_{k-1}<1$, so the remaining is $-1<a_{k-1}\leq0$.
A repairment for that case is using f(f(x)).

Let $f(x)=x^2+x-1$, then $f(f(x))=...=x^4+2x^3-x-1$.
Assume with the supposition $-1<x\leq0$,
[1] $f(f(x))<x$ and [2] $-1<f(f(x))\leq0$ are shown.

Since $a_{k+1}=f(f(a_{k-1}))$, [1] implies $a_{k+1}<a_{k-1}$ and [2] says $a_{k+1}$ also satisfies the supposition, so we can repeat to use [1] to show the chain:
$...a_{k+3}<a_{k+1}<a_{k-1}$, which also gives a contradiction.

Proof for [1] and [2]
[1]: $x-f(f(x))=x-(x^4+2x^3-x-1)=...=(1-x)(1+x)^3,$
which is positive when $-1<x\leq0$.
[2]: From [1] we have $f(f(x))<x\leq0$. For the other side, $f(f(x))-(-1)=x^4+2x^3-x=x(x+1)(x^2+x-1)$,
which will be also found out to be positive with the supposition.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
codyj
723 posts
#11 • 2 Y
Y by samrocksnature, Adventure10
Notice that if we find the right value of $a_1$, our system of equations is less of a system of equations than a system of definitions! Let $f(x)=x^2+x-1$ and $f^k(x)=f(f(\dots f(x)\dots))$ where $f$ is composed $k$ times. We seek all real solutions $x$ to $x=f^n(x)$.

We can prove inductively the following results: For $x>1$, $f^n(x)>x$. For $-1<x<1$, $f^n(x)<x$. For $x<-1$, $f^n(x)>x$. Therefore, the only solutions may occur at $x=\pm1$. Indeed, these are solutions as $f^n(x)=x$. Therefore, the only solutions are $(1,1,\dots,1,1)$ and $(-1,-1,\dots,-1,-1)$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AopsUser101
1750 posts
#12 • 3 Y
Y by v4913, samrocksnature, Mango247
Summing, we see that $\sum _{i = 1} ^ n a_i^2 = n$. We write each equation as $a_i(a_i + 1) = 1 + a_{i + 1}$ for all integer $i \in [1,n-1]$ and $a_n(a_n+1) = a_1$; multiplying all of them yields that $\prod_{i = 1}^n a_i = 1$. By the AM-GM inequality, we know that:
$$\sum_{i = 1}^n a_i^2 \ge n\sqrt[n]{\prod_{i = 1}^n a_i^2}=n$$Since equality clearly holds, $a_1^2 = a_2^2 = ... = a_n^2 = 1$. Plugging in $a_1 = 1$ into the first equation, we see that $a_1 = a_2$ and it follows that $a_1 = a_2 = ... = a_n$. Therefore, we see that the only possible solutions are $a_1 = a_2 = .... = a_n = \pm 1$, which we can check do indeed work.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pad
1671 posts
#13 • 1 Y
Y by samrocksnature
We have
\[ a_{k+1}+1 = a_k(a_k+1).\]Taking the cyclic product over all $k$, we get $a_1\cdots a_n=1$. Taking the cyclic sum of the original sum, we get $a_1^2+\cdots+a_n^2 = n$. By AM-GM, $a_1^2+\cdots+a_n^2 \ge n (a_1\cdots a_n)^{2/n} = n$, and since equality is achieved, $|a_1|=\cdots=|a_n|=1$.

If $a_i=1$ for some $i$, then $a_{i+1}=1$, and so on for all $a$'s, and similarly if $a_i=-1$ then all are -1. So either all are 1 or all are -1.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
wolfpack
1274 posts
#14 • 1 Y
Y by samrocksnature
This solution felt natural and much more easier to find without any high level manipulations.

Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
324 posts
#15 • 2 Y
Y by Emathmaster, samrocksnature
Doesn't seem obviously correct, for values close to $-1$ the sequence can oscillate wildly between things greater than $-1$ and things smaller than $-1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Jay17
268 posts
#16 • 1 Y
Y by samrocksnature
sol
This post has been edited 1 time. Last edited by Jay17, Sep 13, 2020, 9:52 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Zorger74
760 posts
#17 • 1 Y
Y by samrocksnature
Solved with andyxpandy99.

Solution
This post has been edited 1 time. Last edited by Zorger74, Nov 23, 2020, 10:18 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JustKeepRunning
2958 posts
#19
Y by
Very nice problem! Similar flavor to Shortlist 2018 A2, but more intuitive.

The answers are $\{a_i\}=\{1\}$ and $\{a_i\}=\{-1\}.$ These work. Notice that if any one of the $a_i$ is equal to $1$ or $-1,$ the rest must be as well, so from now on, we will assume that no $a_i$ is equal to $1$ or $-1$. Furthermore, there can also be no $a_i=0,$ as that would make $a_{i+1}$(indices taken $\pmod n$) equal to $-1,$ a contradiction.

Summing, we get that $\sum a_i^2 = n,$ and factoring, we get that $a_1(a_1+1)=a_2+1$. Taking the product of cyclic permutations, we get that $\prod a_i(a_i+1)=\prod (a_i+1),$ and since $a_i\neq 0,-1\forall 1\leq i\leq n,$ we have that $\prod a_i = 1$. However, by AM-GM, we have that $\frac{\sum a_i^2}{n}\geq 1,$ and because equality holds, we get that the entire sequence is equal up to sign. From here, it is just a matter of checking cases!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Camilaeon
17 posts
#20
Y by
Summing every equation gives that the sum of the squares of the sequence is exactly n (this means that the quadratic mean is 1). Adding 1 to both sides and multiplying gives that, as long as no number in the sequence is - 1, the product is also 1. However, Q(x) >= A(x) >= G(x) this means that A(x) = 1. Thus the sum of every number in the sequence is n, but this means that the sums of the squares equals the regular sum of every term. This implies that a_i=1 for all i unless it is - 1 for some i.
Going into this second case, if a term is - 1 then the next is also - 1, thus a_n is - 1. This means that a_1 is also - 1 and the whole sequence is - 1.
This post has been edited 1 time. Last edited by Camilaeon, Aug 31, 2021, 8:10 AM
Reason: Correction in the proof
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
303 posts
#21 • 1 Y
Y by centslordm
Let $P(x)=x^2+x-1$. Notice that $a_1=P^n(a_1)$, but by IMO 2006/5 $P^n$ has at most two fixed points which in this case are at $1$ and $-1$. Thus, either $a_1=1$ or $a_1=-1$ for which it follows that all terms are equal.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
324 posts
#22
Y by
blackbluecar wrote:
Let $P(x)=x^2+x-1$. Notice that $a_1=P^n(a_1)$, but by IMO 2006/5 $P^n$ has at most two fixed points which in this case are at $1$ and $-1$. Thus, either $a_1=1$ or $a_1=-1$ for which it follows that all terms are equal.

This solution doesn't work as stated since IMO 2006/5 says that $P^n$ has at most two integer fixed points.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blackbluecar
303 posts
#23
Y by
@above oops yes you are right, thanks for pointing that out. Back to the drawing board :blush:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5005 posts
#24
Y by
The answer is $(1,\ldots,1)$ and $(-1,\ldots,-1)$, both of which clearly work. Take indices modulo $n$, so $a_{k+1}=a_k^2+a_k-1$ (when we say the sequence is periodic, this is by considering the infinite extension of the sequence in periodic manner). We now present two solutions to show that no other $n$-tuples work.

Solution 1 (very bad!!!): If $a_i=-1$ then all of them are $-1$ as well, hence suppose none of them are $-1$. Add one to both sides of the equation to get $a_{k+1}+1=a_k(a_k+1)$. Since no $a_i$ equals $-1$, we have $a_1\ldots a_n=1$. On the other hand, summing gives $a_1^2+\cdots+a_n^2=n$. But by AM-GM we have
$$n=a_1^2+\cdots+a_n^2\geq n(a_1\ldots a_n)^{2/n}=n,$$hence $a_1=\cdots=a_n$, which means all of them are either $1$ or $-1$, so we extract the given answer. $\blacksquare$

Solution 2 (very good!!!) By summing all the equations we have $a_1^2+\cdots+a_n^2=n$, so there must exist some $i$ with $|a_i| \geq 1$. It is clear that if $a_i>1$, $a_{i+1}>a_i$, but this is absurd as it makes a periodic sequence strictly increasing, so we either have $a_i=1$ for all $i$, $a_i=-1$ for all $i$, or there exists some $i$ such that $a_i<-1$. We will show that the third case is impossible. Indeed, suppose $a_i=-1-a$ for $x>0$. Since we have $x^2+x-1 \geq -5/4$ for all $x \in \mathbb{R}$, we must have $a_i \geq -5/4$ for all $i$, hence $a \in (0,1/4]$. Now we can calculate $a_{i+1}=-1+(a^2+a)$, and
$$a_{i+2}=-1-(a-(2a^3+a^4)).$$We can check that $a>2a^3+a^4$ for $a \in (0,1/4]$ (factor it as $a(a+1)(a^2+a-1)<0$), so $a_{i+2}+1$ is also negative but also strictly greater than $a_i+1$. Thus, we have $a_{i+2}>a_i$ for all $i$, but this is again impossible as $(a_i)$ is periodic. From this, we either have $a_i=1~\forall i$ or $a_i=-1~\forall i$the desired solution. $\blacksquare$
This post has been edited 1 time. Last edited by IAmTheHazard, Apr 17, 2022, 2:28 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jasperE3
11395 posts
#25
Y by
Take indices$\pmod n$. We have the equations $a_i^2+a_i=a_{i+1}+1$ for each $i$.
If $a_i=-1$ for any $i$, then:
$$a_{i+1}=a_i^2+a_i-1=-1$$so by induction $(a_1,a_2,\ldots,a_n)=\boxed{(-1,-1,\ldots,-1)}$ which is indeed a solution. Otherwise, suppose that $a_i\ne-1$ for all $i$.

Summing the equations $a_i^2+a_i=a_{i+1}+1$ for $1\le i\le n$ gives:
$$\sum_{i=1}^na_i^2+\sum_{i=1}^na_i=\sum_{i=1}^na_{i+1}+n$$so
$$\sum_{i=1}^na_i^2=n.$$Multiplying these equations gives:
$$\prod_{i=1}^na_i(a_i+1)=\prod_{i=1}^n(a_{i+1}+1)$$so
$$\prod_{i=1}^na_i=1.$$
But by QM-AM, we have:
$$1=\sqrt{\frac1n\sum_{i=1}^na_i^2}\ge\sqrt[n]{\prod_{i=1}^na_i}=1,$$so equality holds and all of the $a_i$ are equal. Rearranging the first equation gives that $a_1^2=1$, and since $a_1\ne-1$ we have $(a_1,a_2,\ldots,a_n)=\boxed{(1,1,\ldots,1)}$ which is indeed a solution.
This post has been edited 1 time. Last edited by jasperE3, Apr 16, 2022, 2:57 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
IAmTheHazard
5005 posts
#26
Y by
jasperE3 wrote:
if $a_i\le-1$ then $a_2\le-1$

If you mean $a_{i+1}$ instead of $a_2$, this is false—take $a_i=-5/4$, so $a_{i+1}=-11/16>-1$. In fact, if $a_i \leq -1$, we have $a_{i+1} \geq -1$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cj13609517288
1926 posts
#27
Y by
Note: The version of the problem I was given asks for the number of solutions, but the solution works out the same either way.

Note that if $a_k=-1$ for any $k$, then everything becomes $-1$. We will add in this case later, so assume that $a_k+1\ne 0$ for now.

First, sum over all $k$ to get
\[a_1^2+a_2^2+\dots+a_n^2=n.\]
Now rewrite our original equation as
\[\frac{a_{k+1}+1}{a_k+1}=a_k\]and multiply over all $k$ to get
\[a_1a_2\dots a_n=1.\]
Thus
\[\sqrt{\frac{a_1^2+a_2^2+\dots+a_n^2}{n}}=\sqrt[n]{a_1a_2\dots a_n}.\]This implies QM-GM for the variables $|a_1|,|a_2|,\dots,|a_n|$ and only has the equality case of everything being equal.

If $x$ goes to $-x$, then $x^2+x-1=-x$ so $x=-1\pm\sqrt2$. We can manually check that for each of these cases, $-x$ doesn't go to either of $x$ or $-x$. Thus the sequences are indeed constant.

Plugging back in, the sequence must be all $1$'s or all $-1$'s, so the answer is $\boxed{2}$.
This post has been edited 8 times. Last edited by cj13609517288, Apr 19, 2023, 6:29 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1541 posts
#28
Y by
If we sum cyclically, we get \[ a_{1}^2 + a_{2}^2 + \dots + a_{n}^2 = n\]Also, note that
\[ a_{k+1} + 1 = a_k(a_k + 1) \]As such, \[ a_1a_2\dots a_n(a_i + 1) = (a_i + 1) \]If $a_i = -1$ for some $i$, then all $a_i$ equal $-1$. Else, assume $a_1a_2\dots a_n = 1$ and no $a_i = -1$. By AM-GM, \[ \frac{a_1^2 + a_2^2 + \dots + a_n^2}{n} \ge \sqrt[n]{a_1^2a_2^2\dots a_n^2} = 1 \]Equality can only hold if $a_1^2 = a_2^2 = \dots = a_n^2 = 1$, so thus $a_1 = a_2 = \dots = a_n = 1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathandski
773 posts
#29
Y by
Subjective Rating (MOHs) $       $
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AshAuktober
1013 posts
#30
Y by
Firstly add all the equations to get $\sum_i a_i^2 = n$
Now, rewrite the equations as $$a_i(a_i + 1) = a_{i+1} + 1.$$$i = 1, 2, \cdots. n$.
Then we have two cases:
Case 1: Some $a_i$ is $-1$.
Then evidently, $$a_{i+1} + 1 = 0 \implies a_{i+1} = -1$$and so on, so $$a_i = -1 \forall i.$$Case 2: No $a_i$ is $-1$.
Take the cyclic product of all the equations to get $$\prod_{i} a_i \cdot \prod_i (a_i + 1) = \prod_i (a_i + 1).$$But $\prod_i (a_i+1) \ne 0$, so $$\prod_{i} a_i  = 1 \implies \prod_i a_i^2 = 1.$$Now AM-GM gives us $$1 = \frac{\sum_i a_i^2}{n} \ge \left(\prod_i a_i^2\right)^{1/n} = 1.$$Since equality holds, $a_1^2 = \cdots = a_n^2 = 1$. But no $a_i$ is $-1$, so all $a_i$ are $1$, yielding $a_i = 1 \forall i$.
Since $\boxed{(a_1, \cdots, a_n) = (-1, \cdots, -1)}$ and $\boxed{(a_1, \cdots, a_n) = (1, \cdots, 1)}$ both clearly work, we're done. $\square$
This post has been edited 2 times. Last edited by AshAuktober, Dec 13, 2024, 12:11 PM
Reason: typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ihatecombin
69 posts
#31
Y by
Claim 1:
\(a_{k+2} = a_{k}^4 + 2a_{k}^3 - a_{k} - 1\)
Proof:
The problem condition is
\[a_{k+1} = a_{k}^2 + a_{k} - 1\]We can substitute this value of \(a_{k+1}\) into the problem condition to obtain
\[a_{k+2} = a_{k+1}^2 + a_{k+1} - 1 = {(a_{k}^2 + a_{k} - 1)}^2 + (a_{k}^2 + a_{k} - 1) -1 = a_{k}^4 + 2a_{k}^3 - a_{k} - 1\]QED

Claim 2:
If \(-1 < a_{k} < 1\), then \(|-1-a_{k}| > |-1-a_{k+2}|\), in other words \(a_{k+2}\) will get closer to \(-1\).
Proof:
We can represent \(a_{k}\) as \(-1+\delta\) for some positive \(\delta < 2\). Substituting this value into the equation for \(a_{k+2}\) gives us
\[a_{k+2} = {(-1+\delta)}^4 + 2{(-1+\delta)}^3 - (-1+\delta) -1 = \delta^4 - 2\delta^3 + \delta - 1\]Our goal is to show that
\[\delta > |-1 - (\delta^4 - 2\delta^3 + \delta - 1)|\]Simplifying, we have
\[|-1 - (\delta^4 - 2\delta^3 + \delta - 1)| = |\delta^4 -2\delta^3 + \delta| = \delta \cdot |(\delta-1)(\delta^2-\delta-1)|\]Thus it suffices to show
\[|(\delta-1)(\delta^2-\delta-1)| < 1\]Which can be bashed. QED

Claim 3:
If \(\frac{-1-\sqrt{5}}{2} < x < - 1\), then \(|-1-a_{k}| > |-1-a_{k+2}|\), in other words \(a_{k+2}\) will get closer to \(-1\).
Proof:
We substitute \(a_{k} = -1 + \delta\) like before, however this time for negative delta (I don't want to reexpand the equation lol). Again it suffices to show
\[-\delta > |\delta(\delta-1)(\delta^2-\delta-1)|\]However notice that
\[-\delta > |\delta(\delta-1)(\delta^2-\delta-1)| \iff 1 > |(\delta-1)(\delta^2-\delta-1)|\]for \(\frac{1-\sqrt{5}}{2}< \delta < 0\). Which is true since \(\frac{1-\sqrt{5}}{2}\) is a root of \((\delta^2-\delta-1)\). QED
Claim 4:
If \(-2< a_{k} < \frac{-1-\sqrt{5}}{2}\), then \(1 > a_{k+2} > - 1\)
Proof:
More boring subs. QED
Claim 5:
If there is an \(a_{k} > 1\), then
\[a_{k+1} > a_{k}\]Also if there is an \(a_{k} < -2\), then \(a_{k+1} > 1\)
Proof:
Easy substitution into the original equation. QED

Let \(n\) denote the \(n\)-th composition of \(x^4+2x^3-x-1\), notice that
\[a_{1} = f^{n}(a_{1})\]Claims 1 until 5 imply that \(a_{1} = \{1,-1\}\). Thus the only possible sequences are \(a_{i} = 1\) for all \(i\) or \(a_{i} = -1\) for all \(i\).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Primeniyazidayi
117 posts
#32
Y by
Nice problem:
If any of them is equal to -1,then all of them are -1.If not,then multiplying the equations gives us that $a_1a_2...a_n=1$.But we have that $\sum_{i=1}^n a_i^2= n$ and defining the sequence $b_i = |a_i|$ gives us $b_i =1$ via AM-GM.This gives us all the results.
This post has been edited 3 times. Last edited by Primeniyazidayi, Apr 3, 2025, 11:39 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
blueprimes
363 posts
#33
Y by
We claim the only solutions are $(a_1, a_2, \dots, a_n) = (-1, -1, \dots, -1), (1, 1, \dots, 1)$ which clearly work.

Now note that any $a_k = -1$ is sufficient enough to imply the solution set $(-1, -1, \dots, -1)$, so assume otherwise. We can rearrange the relation $a_{k + 1} = a_k^2 + a_k - 1$ (indices $\pmod{n}$) to $a_k^2 = a_{k + 1} - a_k + 1$ which summing over all $k$ telescopes to $a_1^2 + a_2^2 + \dots + a_n^2 = n$. Moreover, we also have $\dfrac{a_{k + 1}  + 1}{a_k + 1} = a_k$ which multiplying over all $k$ gives $a_1 a_2 \dots a_n = 1$.

So $\dfrac{|a_1|^2 + |a_2|^2 + \dots + |a_n|^2}{n} = \sqrt[n]{|a_1|^2 |a_2|^2 \dots |a_n|^2}$ which is the equality case of AM-GM. Then $|a_1| = |a_2| = \dots = |a_n|$ easily gives $(1, 1, \dots, 1)$ as a solution set, done.
This post has been edited 2 times. Last edited by blueprimes, Apr 18, 2025, 3:40 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
674 posts
#34
Y by
Addingi all the equations, we get that $\sum a_n^2 = n.$ We also have that $a_{k + 1} + 1 = a_k^2 + a_k,$ and so $\prod a_n = 1.$ Thus, by AM-GM, we have that $a_k = \pm 1.$ If $a_0 = 1,$ then the rest are all 1. If $a_0 = -1,$ the rest are -1.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Maximilian113
575 posts
#36
Y by
Observe that $$a_k=\frac{a_{k+1}+1}{a_k+1}$$so multiplying these yields $\prod a_i = 1.$ Meanwhile $$a_k^2-1 = a_{k+1}-a_k \implies \sum a_i^2 = n.$$But by the Power Mean Inequality $$\sqrt{\frac{\sum a_i^2}{n}} \geq \sqrt[n]{\prod a_i} \iff 1=1$$so equality in fact holds and all $a_i$ are equal. $x^2+x-1=x \iff x=\pm 1$ so the only solutions are $$(a_1, a_2, \dots, a_n) = (1, 1, \dots, 1), (-1, -1, \dots, -1).$$
this felt like 2015 ISL A1
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
torch
1016 posts
#37
Y by
The answer is $\boxed{(a_1, a_2, \dots, a_n)=\pm(1, 1, \dots, 1)}$. Summing the condition over $k$ gives $a_1^2+a_2^2+\dots+a_n^2 = n$. The condition can also be manipulated to $\frac{a_{k+1}+1}{a_k+1}=a_k$, which gives $a_1a_2\dots a_n=1$ by multiplying over $k$. This gives the equality case of AM-GM on $(a_1^2, a_2^2, \dots, a_n^2),$ which implies $a_1=a_2=\dots=a_n=\pm 1$. Note that if $a_k=1$, then $a_{k+1}=1$ as well, and likewise, if $a_k=-1$, then $a_{k+1}=-1$. The result follows by induction.
Maximilian113 wrote:
this felt like 2015 ISL A1
well they're both in alg manip
This post has been edited 2 times. Last edited by torch, Apr 29, 2025, 12:30 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
shendrew7
799 posts
#38
Y by
We claim our only solution are $\boxed{(-1, \ldots, -1), (1, \ldots, 1)}$. We aim to show that there are no other solutions.

Consider dividing the parabola $y=x^2+x-1$ into four regions $A$, $B$, $C$, $D$ with y-coordinates $\ge 1$, $[0,1]$, $[-1,0]$, $\leq -1$. Then we can see that the mapping $x \rightarrow x^2+x-1$ maps
\[A \mapsto A, B \mapsto \text{down}, C \mapsto D, D \mapsto C.\]
We see that the only cycle of length greater than 1 we could have is the involution $C \mapsto D \mapsto C$. Thus the only other solutions we could have are from
\[(x^2+x-1)^2+(x^2+x-1)-1=x \implies (x-1)(x+1)^3 = 0.\]
Thus there are no other solutions. $\blacksquare$
Z K Y
N Quick Reply
G
H
=
a