IMO 2018 Problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

322 posts

#1 h Jul 9, 2018, 11:26 AM • 27 Y

Y by Ziad_09, sa2001, Kayak, ssk9208, Med_Sqrt, anantmudgal09, Muradjl, scrabbler94, Mudkipswims42, scimaths, Carpemath, Amir Hossein, Davi-8191, Durjoy1729, Krypton36, Supercali, potatothegeek, mathleticguyyy, Siddharth03, Desargues123, megarnie, This_deserves_a_like, NO_SQUARES, Adventure10, Mango247, Deadline, deplasmanyollari

Find all integers $n \geq 3$ for which there exist real numbers $a_1, a_2, \dots a_{n + 2}$ satisfying $a_{n + 1} = a_1$ , $a_{n + 2} = a_2$ and
$a_ia_{i + 1} + 1 = a_{i + 2},$ for $i = 1, 2, \dots, n$ .

Proposed by Patrik Bak, Slovakia

This post has been edited 2 times. Last edited by djmathman, Jun 16, 2020, 4:02 AM
Reason: problem author

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

prague123

230 posts

prague123

#3 h Jul 9, 2018, 11:59 AM • 30 Y

Y by fattypiggy123, Wizard_32, Kayak, juckter, Carpemath, me9hanics, biomathematics, Snakes, mastermind.hk16, 277546, mathleticguyyy, samuel, yushanlzp, OlympusHero, Limerent, megarnie, judgefan99, celestialphoenix3768, Kingsbane2139, crazyeyemoody907, a22886, J55406, Newmaths, sabkx, ehuseyinyigit, Adventure10, Assassino9931, Sedro, aidan0626, ihatemath123

Wow, an algebra problem that is neither inequality nor functional equation. We must thank the jury for this choice. I guess that the rest of the algebra part of the shortlist was depressing inequalities and boring functional equations.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

arshakus

769 posts

arshakus

#4 h Jul 9, 2018, 12:01 PM • 2 Y

Y by Carpemath, Adventure10

okay, if there is no solution for more than half an hour, I'm posting the value of $a_i$ for $n=3$ :
Click to reveal hidden text

This post has been edited 1 time. Last edited by arshakus, Jul 9, 2018, 12:03 PM
Reason: add a_i's

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Morskow

46 posts

Morskow

#5 h Jul 9, 2018, 12:04 PM • 73 Y

Y by Itama, ssk9208, mickeydomath, arshakus, L3435, Muradjl, anantmudgal09, Mudkipswims42, Supercali, Plasma_Vortex, nikolapavlovic, hansu, Carpemath, opptoinfinity, yugrey, me9hanics, rkm0959, Mathnerd1223334444, richrow12, BobaFett101, bigplussmallminus, AlbertHawking, tapir1729, IMO2019, WallyWalrus, Pallav123Goyal, p_square, KastavIvan, MYL, nhusanboev, ywq233, AlastorMoody, Ramanujanjr_, Lukaluce, FadingMoonlight, meet18, mathleticguyyy, Siddharth03, Mathasocean, Illuzion, hellomath010118, OlympusHero, Limerent, N1RAV, tigerzhang, mijail, megarnie, IAmTheHazard, Quidditch, Wizard0001, Pluto1708, hakN, JG666, Mop2018, Jalil_Huseynov, a22886, Kingsbane2139, crazyeyemoody907, rama1728, metricpaper, sman96, This_deserves_a_like, Lamboreghini, Adventure10, Mogmog8, sabkx, Stuffybear, Tellocan, Deadline, Sedro, zaidova, aidan0626, Mathlover_1

Written a bit hastily - we view the indices mod 3. We get:
$a_ia_{i+1}a_{i+2}+a_{i+2}=a_{i+2}^2$ $\sum_{i=1}^na_ia_{i+1}a_{i+2}+\sum_{i=1}^na_i=\sum_{i=1}^na_i^2$ $\sum_{i=1}^na_ia_{i+3}=\sum_{i=1}^na_i(a_{i+1}a_{i+2}+1)=\sum_{i=1}^na_i^2$ By the Rearrangement inequality, we get $a_i=a_{i+3}$ for $1\leq i\leq n$ . Therefore, $n$ is divisible by $3$ , else all members of the sequence are equal. $a_{3k+1}=a_{3k+2}=-1, a_{3k+3}=2$ is a valid solution for each integer $0\leq k<\frac{n}{3}$ .

This post has been edited 2 times. Last edited by Morskow, Jul 9, 2018, 1:44 PM
Reason: Clarifying slightly

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Itama

78 posts

Itama

#6 h Jul 9, 2018, 12:12 PM • 5 Y

Y by Carpemath, User19, Adventure10, Mango247, Stuffybear

Morskow wrote:

Written a bit hastily - we view the indices mod 3. We get:
$a_ia_{i+1}a_{i+2}+a_{i+2}=a_{i+2}^2$ $\sum_{i=1}^na_ia_{i+1}a_{i+2}+\sum_{i=1}^na_i=\sum_{i=1}^na_i^2$ $\sum_{i=1}^na_1a_{i+3}=\sum_{i=1}^na_i^2$ By the Rearrangement inequality, we get $a_i=a_{i+3}$ for $1\leq i\leq n$ . Therefore, $n$ is divisible by $3$ , else all members of the sequence are equal. $a_{3k+1}=a_{3k+2}=-1, a_{3k+3}=2$ is a valid solution for each integer $0\leq k\leq\frac{n}{3}$ .

Beautiful solution. I was guessing one should end up with something like this...

Now I expect the marking scheme is going to be once again awful.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

WizardMath

2487 posts

WizardMath

#7 h Jul 9, 2018, 12:16 PM • 6 Y

Y by Mathlover1292, Carpemath, Davi-8191, Pallav123Goyal, Adventure10, Mango247

We see that for every $n$ divisible by $3$ , the solution $(2, -1, -1, 2, -1, -1, ...)$ works. We now show that all such $n$ are divisible by $3$ .
Claim : $a_i$ repeats after every $3$ indices.
Proof : The relation can be written as $a_i a_{i+1} a_{i+2} + a_{i+2} = a_{i+2}^2$ and $a_i a_{i+1} a_{i-1} + a_{i-1} = a_{i+2}a_{i-1}$
Summing these both over all $i$ , we have $\sum_{i=2}^{n+1} a_{i+2}a_{i-1} = \sum_{i=2}^{n+1} a_{i-1}^2$
But we also have $a_{i+2}a_{i-1} \le \frac{a_{i+2}^2 +a_{i-1}^2}{2}$ . Summing over $i$ from $2$ to $n+1$ , we have that $\sum_{i=2}^{n+1} a_{i+2}a_{i-1} \le \sum_{i=2}^{n+1} a_{i-1}^2$
Since equality holds, our claim is proved.
Now assume we don't have a cycle divisible by 3, then eventually we must have all elements equal, so $a^2 - a + 1 = 0$ , which has no real solutions. So $3|n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MS_Kekas

275 posts

MS_Kekas

#8 h Jul 9, 2018, 12:20 PM • 7 Y

Y by Carpemath, yugrey, ywq233, bigboo, Jalil_Huseynov, Adventure10, Mango247

Answer is for $n\vdots 3$ .
Example:
$a_0 = a_1 = -1$ .

Now suppose there is one with $3$ not dividing $n$ .
Note that we can extend the sequence as far as we want. The question is to find all possible lengths of the cycle of the sequence.
Suppose at the moment we have two adjacent nonnegative numbers in the sequence. Suppose they are $a_0, a_1\ge0$ .

Now note that every following $a_i$ is not less than $1$ . That means that if $a_0, a_1$ both meet in the sequence again, they are not less than one.

But then note that for each $i\ge2$ $a_{i}>a_{i-1}$ . That means that $min(a_0, a_1)$ will not occur any more.

Now suppose that we don't have two adjacent nonnegative numbers. Start from negative $a_0, a_1$ then if we have one. We see that $a_2>1$ .
Then $a_3<0$ . Notice that if $a_4=a_2a_3+1>0$ , then $a_5 = a_4a_3+1>a_3a_2+1=a_4\ge0$ , as $a_3<0$ and $a_4 = a_3a_2+1\le1<a_2$ . Contradiction: $a_5, a_4\ge 0$ .
So we get that if $a_2>1$ then $a_3<0, a_4<0$ . So $a_5>1$ . Now we are having a cycle, in which every third number in positive. That means that the length of the cycle must be of the form $3k$ .

Now suppose we don't even have consecutive negative numbers. That means that we have like $nonnegative, negative, nonegative, negative, ....$ . Suppose $a_0, a_2,\cdots \ge0, a_1, a_3,\cdots <0$ . Then notice that each nonnegative number $a_{2i} = a_{2i-1}a_{2i-2} +1\le1$ . That means that $a_{2i+1} = a_{2i}a_{2i-1} +1 >a_{2i-1}+1$ . So negative nnumbers only increase, and the cycle cannot occur.

This post has been edited 1 time. Last edited by MS_Kekas, Jul 9, 2018, 12:21 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.

Skender

30 posts

Skender

#9 h Jul 9, 2018, 12:21 PM • 4 Y

Y by bigplussmallminus, Carpemath, Adventure10, Mango247

BIG plus small minus!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

test20

988 posts

test20

#10 h Jul 9, 2018, 12:28 PM • 6 Y

Y by Kayak, Carpemath, me9hanics, Siddharth03, Adventure10, ihatemath123

prague123 wrote:

Wow, an algebra problem that is neither inequality nor functional equation. We must thank the jury for this choice. I guess that the rest of the algebra part of the shortlist was depressing inequalities and boring functional equations.

I think that the problem actually is an inequality that is hidden behind a clumsy functional equation (function $f$ from $\{1,\ldots,n\}$ to the real numbers).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Orestis_Lignos

555 posts

Orestis_Lignos

#11 h Jul 9, 2018, 12:32 PM • 5 Y

Y by Carpemath, Chokechoke, rstenetbg, Adventure10, Mango247

Hope that I dont have tha same sol as anyone above.

We have $a_1a_2+1=a_3 \Rightarrow a_1a_2a_3=a_3^2-a_3$ so $a_ia_{i+1}a_{i+2}=a_{i+2}^2-a_i$ for all $i=1,2, \ldots, n$ .

So, $a_1a_2a_3+a_2a_3a_4+ \ldots+ a_{n}a_{n+1} a_{n+2}=\sum a_i^2-\sum a_i$ Also, $a_1a_2a_3+a_1=a_1a_4$ etc, so $a_1a_4+a_2a_5+ \ldots+a_na_{n+3}=a_1^2+a_2^2+ \ldots a_n^2$ , where $a_{n+3}=a_1$ . By AM-GM, $a_{j}a_{j+3} \leqslant \dfrac{a_{j}^2+a_{j+3}^2}{2}$ so applying that, we get equality, so $a_j=a_{j+3}$ .

If now $n$ is not $\equiv 0 \pmod 3$ , we have two cases. If $n \equiv 1 \pmod 3$ : $a_1=a_4=a_7= \ldots=a_{n}=a_{3}= \ldots$ so eventually all $a_i$ are equal, so $a_1=a_1^2+1 \geqslant 2a_1>a_1$ , absurd.
Similarly, $n \equiv 2 \pmod 3$ is impossible, so $n=3k$ and we can easily construct an example, for example $(2,-1,-1)$ for $k$ times.

So $n=3k, \, k \in \mathbb{N}$ is the only solution to the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SHARKYKESA

436 posts

SHARKYKESA

#12 h Jul 9, 2018, 12:34 PM • 4 Y

Y by Carpemath, me9hanics, Adventure10, Mango247

Orestis_Lignos wrote:

Hope that I dont have tha same sol as anyone above.

We have $a_1a_2+1=a_3 \Rightarrow a_1a_2a_3=a_3^2-a_3$ so $a_ia_{i+1}a_{i+2}=a_{i+2}^2-a_i$ for all $i=1,2, \ldots, n$ .

So, $a_1a_2a_3+a_2a_3a_4+ \ldots+ a_{n}a_{n+1} a_{n+2}=\sum a_i^2-\sum a_i$ Also, $a_1a_2a_3+a_1=a_1a_4$ etc, so $a_1a_4+a_2a_5+ \ldots+a_na_{n+3}=a_1^2+a_2^2+ \ldots a_n^2$ , where $a_{n+3}=a_1$ . By AM-GM, $a_{j}a_{j+3} \leqslant \dfrac{a_{j}^2+a_{j+3}^2}{2}$ so applying that, we get equality, so $a_j=a_{j+3}$ .

If now $n$ is not $\equiv 0 \pmod 3$ , we have two cases. If $n \equiv 1 \pmod 3$ : $a_1=a_4=a_7= \ldots=a_{n}=a_{3}= \ldots$ so eventually all $a_i$ are equal, so $a_1=a_1^2+1 \geqslant 2a_1>a_1$ , absurd.
Similarly, $n \equiv 2 \pmod 3$ is impossible, so $n=3k$ and we can easily construct an example, for example $(2,-1,-1)$ for $k$ times.

So $n=3k, \, k \in \mathbb{N}$ is the only solution to the problem.

Can't apply AM-GM since we're working in reals, not positive reals. However, rearrangement will work fine.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Orestis_Lignos

555 posts

Orestis_Lignos

#13 h Jul 9, 2018, 12:36 PM • 3 Y

Y by Carpemath, Adventure10, Mango247

SHARKYKESA wrote:

Orestis_Lignos wrote:

Hope that I dont have tha same sol as anyone above.

We have $a_1a_2+1=a_3 \Rightarrow a_1a_2a_3=a_3^2-a_3$ so $a_ia_{i+1}a_{i+2}=a_{i+2}^2-a_i$ for all $i=1,2, \ldots, n$ .

So, $a_1a_2a_3+a_2a_3a_4+ \ldots+ a_{n}a_{n+1} a_{n+2}=\sum a_i^2-\sum a_i$ Also, $a_1a_2a_3+a_1=a_1a_4$ etc, so $a_1a_4+a_2a_5+ \ldots+a_na_{n+3}=a_1^2+a_2^2+ \ldots a_n^2$ , where $a_{n+3}=a_1$ . By AM-GM, $a_{j}a_{j+3} \leqslant \dfrac{a_{j}^2+a_{j+3}^2}{2}$ so applying that, we get equality, so $a_j=a_{j+3}$ .

If now $n$ is not $\equiv 0 \pmod 3$ , we have two cases. If $n \equiv 1 \pmod 3$ : $a_1=a_4=a_7= \ldots=a_{n}=a_{3}= \ldots$ so eventually all $a_i$ are equal, so $a_1=a_1^2+1 \geqslant 2a_1>a_1$ , absurd.
Similarly, $n \equiv 2 \pmod 3$ is impossible, so $n=3k$ and we can easily construct an example, for example $(2,-1,-1)$ for $k$ times.

So $n=3k, \, k \in \mathbb{N}$ is the only solution to the problem.

Can't apply AM-GM since we're working in reals, not positive reals. However, rearrangement will work fine.

No, we can, because AM-GM inequality ( $x^2+y^2 \geqslant 2xy$ ) is written $(x-y)^2 \geqslant 0$ , holds for all reals. Don't get what you say?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Skender

30 posts

Skender

#14 h Jul 9, 2018, 12:45 PM • 11 Y

Y by bigplussmallminus, Itama, IMO2019, Carpemath, FieldBird, Smita, sa2001, ywq233, Infinityfun, Adventure10, sabkx

Can someone please check this “solution”?

So, $3|n$ works, for the above reasons.

Now, no 0’s can occur, otherwise we would have $0, 1, 1, 2, 3, ...$ which doesn’t work. So let’s check the signs of the $a_i$ s.

We can’t have ++, otherwise all the other would be +, and so all would be >1 (because positive*positive+1>1) and so all would be greater than the previous - contradiction;

If we have - -, then the next is + (just use the formula);

If we have - +, then the next is - (we can’t have 2 consecutive +);

If we have + -, the next is -:
PROOF: If the next is +, then the sequence is always alternating (Case 1) or we’ll get a string - - + - + (Case 2).

Case 1: In this case, let $a_{\text{odd}}<0$ and $a_{\text{even}}>0$ , WLOG. Then, we have $a_3<a_4 \Leftrightarrow a_1a_2+1<a_2a_3+1 \Leftrightarrow a_1<a_3$ , so the odds are increasing, contradiction.

Case 2: Let’s call a number BIG if it’s distance to 0 is more than 1, and small if the distance is less than 1.
Then, the first plus is a BIG plus, since it’s 1 plus a product of negatives. The other plus is a small plus, since it’s 1 plus a product positive*negative. The 3rd minus is a small minus, otherwise it’s product with the big plus would be a big negative, and so the last plus would be a minus.
So, the last two are small minus and small plus. Then, their produtc is small minus, and their product +1 is a plus. So we have - - + - + +, contradiction, because we can’t have + +.

Then, we can only have + - - ... + - -, which is a multiple of 3, QED.

Tell me this works :p

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

XxProblemDestroyer1337xX

33 posts

XxProblemDestroyer1337xX

#15 h Jul 9, 2018, 12:55 PM • 13 Y

Y by Snakes, microsoft_office_word, Carpemath, Anzoteh, rmtf1111, L.Bill, anyone__42, Illuzion, This_deserves_a_like, Kingsbane2139, sabkx, Adventure10, Mango247

Here's how to crack it:

For $n \vdots 3$ repeat $(2,-1,-1)$ . Otherwise:
All indices are taken mod n.
Claim: There is no $a_i=0$ . Suppose there is, then $a_{i+1}=1$ , $a_{i+2}=1$ and so on. This sequence grow arbitrarily large thus contradiction.

Denote by $+$ a positive and by $-$ a negative.

Claim: There is no $++$ . Suppose here is, thus $a_i>0, a_{i+1}>0$ . Then $a_{i+2}>1, a_{i+3}>2$ and so on, it grows arbitrarily thus contradiction.

Claim: There is no $---$ . This is trivial.

Thus every $+$ has exactly $1$ or $2$ of $-$ in front and behind them.

Claim: There is a $+-+$ . Otherwise all $+$ have exactly $2$ of $-$ behind and in front of them, thus $n \vdots 3$

Claim: In a $+-+$ , both of the positives are smaller than $1$ .
Obviously the second $+$ is followed by a $-$ . Let the first number be $x$ and the second $-y$ , where $x,y>0$ . Then the third is $-xy+1$ and the fourth is $xy^2-y+1$ . Now: $xy^2-y+1<0 => 0 < x < \dfrac{1-y}{y^2} => y>1$ . $-xy+1>0 => x<\dfrac{1}{y}<1$ . Obviously $-xy+1<1$ . Thus both positives are smaller than $1$ .

Claim: In a $--+$ the positive is bigger than $1$ . This is obvious.

Now, assume we have a $--+$ in the sequence. The $+$ is $>1$ . If the $+$ is followed by exactly one $-$ then it is $<1$ -contradiction. Thus it is followed by two $-$ . Thus we have another $--+$ . Keep doing this, thus the whole sequence is $--+--+--+...--+$ , thus $n \vdots 3$ - contradiction. So we don't have a $--+$ , then our sequence is $+-+-+-...+-$ . But (credit to rmtf1111):
Let $a_{i+1}>0$ .
$a_i\cdot a_{i+1}+1<0 => a_i<\dfrac{-1}{a_{i+1}}, a_{i+1}\cdot a_{i+2}+1>0 => a_{i+2}>\dfrac{-1}{a_{i+1}}$ . Thus $a_i < a_{i+2}$ . So $a_1 < a_3 < .. < a_1$ - contradiction.

This post has been edited 5 times. Last edited by XxProblemDestroyer1337xX, Jul 9, 2018, 6:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Itama

78 posts

Itama

#16 h Jul 9, 2018, 12:58 PM • 4 Y

Y by Skender, Carpemath, Adventure10, Mango247

Skender wrote:

Can someone please check this “solution”?

So, $3|n$ works, for the above reasons.

Now, no 0’s can occur, otherwise we would have $0, 1, 1, 2, 3, ...$ which doesn’t work. So let’s check the signs of the $a_i$ s.

We can’t have ++, otherwise all the other would be +, and so all would be >1 (because positive*positive+1>1) and so all would be greater than the previous - contradiction;

If we have - -, then the next is + (just use the formula);

If we have - +, then the next is - (we can’t have 2 consecutive +);

If we have + -, the next is -:
PROOF: If the next is +, then the sequence is always alternating (Case 1) or we’ll get a string - - + - + (Case 2).

Case 1: In this case, let $a_{\text{odd}}<0$ and $a_{\text{even}}>0$ , WLOG. Then, we have $a_3<a_4 \Leftrightarrow a_1a_2+1<a_2a_3+1 \Leftrightarrow a_1<a_3$ , so the odds are increasing, contradiction.

Case 2: Let’s call a number BIG if it’s distance to 0 is more than 1, and small if the distance is less than 1.
Then, the first plus is a BIG plus, since it’s 1 plus a product of negatives. The other plus is a small plus, since it’s 1 plus a product positive*negative. The 3rd minus is a small minus, otherwise it’s product with the big plus would be a big negative, and so the last plus would be a minus.
So, the last two are small minus and small plus. Then, their produtc is small minus, and their product +1 is a plus. So we have - - + - + +, contradiction, because we can’t have + +.

Then, we can only have + - - ... + - -, which is a multiple of 3, QED.

Tell me this works :p

EXELENT!!! I like it! It works...

What is left is to provide an example and Q.E.D.

This post has been edited 1 time. Last edited by Itama, Jul 9, 2018, 12:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math_comb01

662 posts

math_comb01

#94 h Jan 2, 2024, 4:24 PM

Y by

Cool Problem!
We claim that the answer is $3|n$ ; having construction $(-1,2,-1,-1,2,-1 \cdots -1,2,-1)$ .
Clearly all the $a_i$ cannot be equal. Notice:
$a_{i+2}(a_{i}a_{i+1}+1)=(a_{i+2})^2$ $a_i(a_{i+1}a_{i+2}+1)=(a_i)(a_{i+3})$ subtracting these equations yield
$a_{i+2}+a_{i+1}a_{i+3}=a_{i+2}^2+a_i$ summing over cyclically gives
$\sum_{cyc} a_i^2 = \sum_{cyc} a_ia_{i+3}$ which is equivalent to
$\sum_{cyc} (a_i-a_{i+3})^2= 0$ which implies if $3$ does not divide $n$ ; then all the numbers are equal, which is a clear contradiction!. Hence the claimed $n$ only work

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

597 posts

eibc

#95 h Jan 4, 2024, 10:39 PM

Y by

The answer is all $n$ such that $3 \mid n$ . For such $n$ , take $a_i = 2$ if $3 \mid i$ and $a_i = -1$ otherwise, which can be verified to work.

To prove these are the only such $n$ , we note that $a_{i + 1}a_{i + 2} + 1 = a_{i + 3}$ , and multiplying both sides of this by $a_i$ gives $a_ia_{i + 3} - a_i = a_ia_{i + 1} a_{i + 2} = a_{i + 2}(a_{i + 2} - 1) = a_{i + 2}^2 - a_{i + 2}$ , or $a_{i + 2}^2 - a_ia_{i + 3} - a_{i + 2} + a_i = 0$ . Cyclically summing this result (and letting $a_{n + 3} = a_3$ ) gives
$\begin{align*} \sum_{i = 1}^n a_i^2 - \sum_{i = 1}^n a_ia_{i + 3} &= \frac{1}{2} \left(\sum_{i = 1}^n (a_i^2 - 2a_ia_{i + 3} + a_{i + 3}^2)\right) \\ &= \frac{1}{2} \left(\sum_{i = 1}^n (a_i - a_{i + 3})^2 \right) \\ &= 0. \end{align*}$ Thus if $i \equiv j \pmod 3$ , then $a_i = a_j$ . If $3 \nmid n$ , then the sequence $1, 4, 7, \ldots$ hits every residue modulo $n$ so all the $a_i$ are equal, but this gives imaginary solutions. If $3 \mid n$ then we can use the aforementioned sequence, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

315 posts

blueprimes

#96 h Jan 22, 2024, 2:49 PM

Y by

We claim that the only $n$ that works are multiples of $3$ . Multiplying the general recursion by $a_{i + 2}$ yields $a_i a_{i + 1} a_{i + 2} + a_{i + 2} = a_{i + 2}^2$ . Then
$\sum_{i = 1}^n a_i a_{i + 1} a_{i + 2} = \sum_{i = 1}^n (a_{i + 2}^2 - a_{i + 2}) \implies \sum_{i = 1}^n a_i a_{i + 1} a_{i + 2} = \sum_{i = 1}^n a_i^2 - \sum_{i = 1}^n a_i$ Now we can "re-link" the terms to obtain the summation
$\sum_{i = 1}^n (a_i a_{i + 1} a_{i + 2} + a_i) = \sum_{i = 1}^n a_i a_{i + 3} = \sum_{i = 1}^n a_i^2$ $\implies \sum_{i = 1}^n (a_i - a_{i + 3})^2 = 0.$ If $3$ divides $n$ , let $n = 3k$ for some positive integer $k$ . We have $a_1 = a_4 = \dots = a_{3k - 2}, a_2 = a_5 = \dots = a_{3k - 1}, a_3 = a_6 = \dots = a_{3k}$ . Observe that we can set these common equal values as $2, -1, -1$ respectively, yielding a valid solution. On the other hand if $3$ does not divide $n$ , all $a_i$ are equal, so $a_1^2 + 1 = a_1$ which has no real solutions. Our proof is complete.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

OronSH

1728 posts

OronSH

#97 h Jan 23, 2024, 1:25 PM • 1 Y

Y by megarnie

The answer is $n\equiv 0\pmod 3.$ For the construction take $a_{3k+1}=a_{3k+2}=-1,a_{3k}=2.$ Now notice that if $a_i,a_{i+1}>0$ we have $a_{i+2},a_{i+3}>1$ and for $j\ge 3$ we have $a_{i+j+1}>a_{i+j},$ impossible. Also if $a_i=0$ we have $a_{i+1}=a_{i+2}=1,$ contradiction from earlier. Now if we consider the indices of the positive $a_i$ we see that they cannot be adjacent and two that are consecutive cannot be spaced by more than $2$ since if $a_i,a_{i+1}$ are negative then $a_{i+2}$ is positive. Now if $n \not\equiv 0\pmod 3$ we can see that there must be some $a_i=a,a_{i+1}=-b,a_{i+2}=1-ab$ with $a,b,1-ab$ positive. Of these choose the maximal $b.$ If $b\le 1$ we have $a_{i+3}=1+b(ab-1).$ However since $a,b>0$ we have $0<ab<1$ so $ab-1>-1$ and $1+b(ab-1)>0,$ impossible since this implies $a_{i+2},a_{i+3}$ both positive. Now if $b>1$ we have $a_{i-1}=-\frac{b+1}a$ and $a_{i-2}=\frac{a(1-a)}{b+1}.$ Now we have $a_{i-2}>0,a_{i-1}<0,a_i>0,$ but $1-ab>0$ gives $1+b-ab>0$ which gives $\frac{b+1}a>b,$ contradicting maximality finishing.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1318 posts

dolphinday

#98 h Jan 23, 2024, 7:53 PM

Y by

Multiply by $a_{i+2}$ to get
$a_ia_{i+1}a_{i+2} + a_{i+2} = a_{i+2}^2 \implies$
$\sum_{i=1}^{n} a_ia_{i+1}a_{i+2} \sum_{i=1}^{n} a_{i+2} = \sum_{i=1}^{n} a_{i+2}^2$ $\implies \sum_{i=1}^{n} a_ia_{i+1}a_{i+2} = \sum_{i=1}^{n} a_{i}^2 - \sum_{i=1}^{n} a_{i}$ $\implies \sum_{i=1}^{n} a_i(a_{i+1}a_{i+2} + 1) = \sum_{i=1}^{n} a_{i}^2 = \sum_{i=1}^{n} a_ia_{i+3}$ $\implies \sum_{i=1}^{n} (a_i - a_{i+3})^2 = 0$ Hence, every $3$ rd term must be equal.
So $3 | n$ , or all $a_i$ are equal.
If all $a_i$ are equal, then $x^2 + 1 = x$ has no solutions, so $3 | n$ must be true.
$\newline$

Our construction for $3 | n$ is
$(-1, -1, 2, -1, -1, 2, \dots, 2)$ .

This post has been edited 2 times. Last edited by dolphinday, Jan 31, 2024, 10:29 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dkedu

180 posts

dkedu

#99 h Jan 27, 2024, 6:58 PM

Y by

We claim multiples of $3$ work just by repeating the sequence $(2, -1, -1)$ .

It is obvious that $0$ cannot occur since this would cause all the terms to be positive and grow arbitrarily large. Therefore $1$ cannot occur since it implies that $0$ occurs as one of the previous two terms.

Now it is obvious that we cannot have two positive numbers in a row for similar reasons to above. Now if we have two negatives, by definition the next term must positive and if we have negative then positive, the next term must be negative since we cannot have two positives in a row.

Claim: We cannot have the sequence, positive, negative, positive.

We get the cases where it alternates forever between positive and negative or it starts with two negatives and then alternates between positive and negative before having two negatives again.

Case 1: We get that the positive numbers must always be increasing which gives a contradiction since they will eventually repeat.

Case 2: If this sequence goes negative, negative, positive, negative, positive, we get that the first positive must be greater than $1$ and the second positive must be less than $1$ . But we can also get that the negative between the two positives must be less that $-1$ since the term after the second positive is still a negative. But then we get a term greater than $1$ multiplied by a term less than $-1$ is greater than $-1$ which is a contradiction so we are done.

Since the sequence must go negative, negative, positive, we have shown $3 \mid n$ and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jp62

53 posts

jp62

#100 h Feb 4, 2024, 2:53 AM

Y by

I claim that $n$ satisfies the condition iff $n$ is a multiple of $3$ . This is achieved with $a_i=-1$ for $3\nmid i$ and $a_i=2$ for $3\mid i$ , which works as $(-1)(-1)+1=2$ and $(-1)(2)+1=-1$ .

Now we show that if $3\mid n$ is necessary. View $\{a_i\}$ as an infinite periodic sequence with period $n$ (take indices mod $n$ ). Denote a positive $a_i$ by $+$ and a negative $a_i$ with $-$ , and write the string of $+$ and $-$ and $0$ symbols. We show the following:

We cannot have + +
We cannot have any zeros
We cannot have an infinite repeating sequence of + -
We cannot have the sequence - - -
We cannot have the sequence - - + - + -

Now we just need to show that the exclusion of all these sequences implies $3\mid n$ . Indeed, since there is no $++$ , every $+$ must be preceded and followed by a $-$ . If there exists a $+-+$ sequence, this must be preceded and followed by a $-$ , thus giving $-+-+-$ . And since this cannot be preceded by a $-$ , we get $+-+-+-$ . But continuing this logic, this must always be preceded by $+-$ . Extending this all the way to $n$ terms and applying periodicity we end up with either a conflict if $n$ is odd or an infinite repeating sequence of $+-$ , which violates (3).

From this we conclude that the only possibility is for every $+$ to be followed by two $-$ s, and since $---$ cannot exist, we get a periodic sequence of $+--$ . For this to align, we must have that $3\mid n$ as that is the minimal period of the sequence. So we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Pyramix

419 posts

Pyramix

#101 h Apr 10, 2024, 10:29 AM

Y by

MiniClaim1: Two consecutive terms cannot both be positive.
Proof. Suppose for contradiction there are consecutive two positive terms, say $a_1,a_2$ . Then, $a_3$ is positive. Since $a_2,a_3$ are positive, $a_4$ is positive. Then, all numbers become positive. But then every term is also more than 1 but we also have $a_2>a_1a_0$ , $a_3>a_2a_1$ , \ldots, $a_1>a_0a_{-1}$ . Multiplying, we get $a_1a_2\cdots a_n<1$ which is impossible as all numbers are more than 1.

MiniClaim2: No term can be 0.
Proof. Suppose $a_1=0$ . Then, $a_2=1,a_3=1$ which gives two consecutive positive terms - impossible.

MiniClaim3: Three consecutive terms cannot be both negative.
Proof. Suppose $a_1, a_2, a_3<0$ . But then $a_3=1+a_1a_2>1$ , so we get contradiction.

MiniClaim4: If $a_i, a_{i+1}$ are both negative, then $a_{i+4}$ is also negative.
Proof. Let $i=1$ . If $a_1, a_2$ are negative then $a_3=1+a_1a_2>1$ which forces $a_4<0$ by MiniClaim1. Suppose it was possible that $a_5>0$ . Then, $a_6<0$ is forced or else two consecutive terms are positive. So, $1+a_4a_5<0$ and $1+a_3a_4>0$ which means $a_5>a_3$ . But $a_5=1+a_3a_4>a_3$ which means $a_3<1$ but then $a_3=1+a_1a_2>1$ , so we have contradiction.
It follows that if $a_i<0,a_{i+1}<0$ then sequence runs like: $\text{negative},\text{negative},\text{positive},\text{negative},\text{negative},\text{positive},\text{negative},\text{negative},\text{positive},\ldots \ \ \ \ (\star)$ and that forces $3\mid n$ as $a_i$ and $a_{i+3}$ have same sign.

Consider a sequence where no consecutive terms are negative nor positive. So, any consecutive terms have different sign. Then, the sequence will proceed like $\text{negative},\text{positive},\text{negative},\text{positive}$ . We show that this is impossible. Suppose possible. Then, if $a_i$ is positive, then $a_{i+2}=1+a_ia_{i+1}<1$ . So all positive terms are in $(0,1)$ . Choose the smallest element, say $a_M$ . Then, $a_M<0$ and we have $-a_{M-2}=\left(\frac{1-a_M}{a_{M-1}}\right)>\frac{-a_M}{a_{M-1}}>-a_M$ which means $a_M>a_{M-2}$ , a contradiction.

So, only sequence possible is the $(\star)$ sequence. The construction:
$-1,-1,2,-1,-1,2\ldots$ works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SenorSloth

37 posts

SenorSloth

#102 h Jun 9, 2024, 1:50 AM • 1 Y

Y by OronSH

We claim that the answer is $3\mid n$ only. The construction is repeating $-1,-1,2$ as many times as needed, which clearly works.

Now we show that no other values work. First, we show that no two positive numbers may be consecutive. FTSOC assume $a_i$ and $a_{i+1}$ are positive. Once you have two consecutive positive numbers, everything after that must have a value greater than $1$ , so in order to loop back around, $a_i$ and $a_{i+1}$ must be greater than $1$ . However, this forces the sequence to be strictly increasing, which clearly won't loop around, contradiction. This also tells us no term can be $0$ , because if $a_i=0$ then $a_{i+1}=a_{i+2}=1$ , which is not allowed.

Now we show that if two consecutive terms are negative, which we call $a_i$ and $a_{i+1}$ , then $a_{i+2}$ is positive and $a_{i+3}$ and $a_{i+4}$ are negative, and then the pattern repeats. $a_{i+2}>1$ since $a_ia_{i+1}$ is positive. We know from above that this forces $a_{i+3}$ to be negative. FTSOC assume $a_{i+4}$ is positive. Since $a_{i+2}>1$ , this would force $\lvert a_{i+3}\rvert<1$ . Since $a_{i+2}a_{i+3}$ is negative yet $a_{i+4}$ is positive, we know that $a_{i+4}<1$ . However, this means that $a_{i+5}=a_{i+3}a_{i+4}+1$ is positive, so there are consecutive positive terms, contradiction. Thus, if there are two consecutive negatives at any point, then the whole sequence repeats the pattern of two negatives followed by a positive, which would force the number of terms to be divisible by $3$ .

There is only one other potential case, which is when the terms alternate in sign. Assume that $a_{i}$ is positive and $a_{i+1}$ is negative, and the sequence alternates from then on. Since $a_{i+3}$ is negative while $a_{i+2}$ is positive, we require that $a_{i+1}a_{i+2}<a_ia_{i+1}$ , and since $a_{i+1}$ is negative this implies that $a_{i+2}>a_i$ . However, repeatedly applying this tells us that the positive terms are strictly increasing, which is a contradiction since we can never loop back around.

Thus, $3\mid n$ is the only possibility, as desired.

This post has been edited 1 time. Last edited by SenorSloth, Jun 9, 2024, 1:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathandski

727 posts

Mathandski

#103 h Sep 11, 2024, 10:00 PM

Y by

Subjective Rating (MOHs) $\text{[math]}$

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megahertz13

3177 posts

megahertz13

#104 h Nov 3, 2024, 1:30 AM • 1 Y

Y by kilobyte144

The answer is $n\equiv 0\pmod 3$ .

Proof that these $n$ satisfy the condition. Take the sequence $(a_1,a_2,\dots_{a_{n+2}})=(-1,-1,2,-1,-1,2,-1,-1,2,\dots,-1,-1,-2,-1,-1),$ which works as $-1\cdot -1 + 1 = 2$ and $-1\cdot 2 + 1 = -1.$
Proof that other $n$ fail. Note that $a_ka_{k+1}a_{k+2}=(a_{k+2}-1)(a_{k+2})=a_{k+2}^2-a_{k+2}.$ It is also equal to $a_k(a_{k+3}-1)=a_ka_{k+3}-a_k.$ Therefore, $a_ka_{k+3}-a_k=a_{k+2}^2-a_{k+2}.$ Summing this for all $k=1,2,\dots,n$ (indices $\pmod n$ ), we know that $\sum a_ka_{k+3}=\sum a_k^2,$ or $\sum2a_ka_{k+3}=2\sum a_k^2.$ To finish the problem, we know that $2\sum a_k^2=\sum(a_k^2+a_{k+3}^2),$ so $\sum(a_k^2+a_{k+3}^2)-2\sum(a_ka_{k+3})=0.$ This implies that $\sum (a_k-a_{k+3})^2 = 0,$ or $a_k = a_{k+3}$ . The sequence now has a period of $3$ , so $n\equiv 0\pmod 3$ . If $n$ is not a multiple of $3$ , all the terms would be equal. This is impossible as $a_i^2+1=a_i$ does not have real roots.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonesPenguin

123 posts

SomeonesPenguin

#105 h Nov 23, 2024, 10:48 AM

Y by

This is way to easy for P2 but whatever.

Notice that $a_ia_{i+1}a_{i+2}+a_{i+2}=a_{i+2}^2$ And $a_ia_{i+1}a_{i+2}+a_i=a_{i+3}a_i$ This implies that $a_{i+2}^2-a_{i+2}=a_ia_{i+3}-a_i$ Summing this over all $i$ gives $\sum(a_{i+3}-a_i)^2=0$ So $a_i=a_{i+3}$ for all $i$ . In particular, if $3\nmid n$ we get $a_1=a_2=\dots=a_n$ which can be easily checked to yield a contradiction. If $3\mid n$ we can pick $a_k=\begin{cases} -1 & k\equiv 1,2\pmod 3\\ 2 & k\equiv 0 \pmod 3 \end{cases}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

517 posts

Maximilian113

#106 h Jan 18, 2025, 4:47 AM

Y by

Note that $a_ia_{i+1}a_{i+2}=a_{i+2}^2-a_{i+2}, \text{ and } a_ia_{i+1}a_{i+2} = a_i a_{i+3}-a_i \implies a_{i+2}^2-a_{i+2}=a_i a_{i+3}-a_i.$ Cyclically summing these gives $2\sum a_i a_{i+3} = 2\sum a_i^2 = \sum (a_i^2+a_{i+3}^2) \implies \sum (a_i-a_{i+3})^2=0.$ Therefore, $a_i=a_{i+3}.$ Note that if $3 \not | n,$ then all the $a_i$ are equal which is impossible as $x^2-x+1=0$ has no real roots. However, if $3|n$ this works by considering the construction $a_{3k}=-1, a_{3k+1}=-1, a_{3k+2}=2.$ Hence, $n \equiv 0 \pmod 3$ are the only solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Novmath

8 posts

Novmath

#107 h Mar 16, 2025, 6:55 PM

Y by

Guys why are you posting your solutions ,which are basically the same as upper-ones.Very interesting problem!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Marcus_Zhang

958 posts

Marcus_Zhang

#108 h Mar 26, 2025, 3:22 AM

Y by

Novmath wrote:

Guys why are you posting your solutions ,which are basically the same as upper-ones.Very interesting problem!

https://artofproblemsolving.com/community/c5h2145086_campp_posting_recs_by_mods states that:

V_Enhance wrote:

It is always permitted to post a full solution to any problem in its own thread (linked above), regardless of how old the problem is, and even if this solution is similar to one that has already been posted. We encourage this type of posting because it is helpful for the user to explain their solution in full to an audience, and for future users who want to see multiple approaches to a problem or even just the frequency distribution of common approaches.

Anyways...

This post has been edited 1 time. Last edited by Marcus_Zhang, Mar 26, 2025, 3:22 AM

Z K Y