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.

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

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}$.

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.

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$.

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.

BIG plus small minus!

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).

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.

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.

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?

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

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.

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.

Show that a1.....an<1 similarly if ai>=0 then ai+1<0. Now it follows the +--+-- which is divisible by 3 and we are done. I forgot n eqiv 0 mod 3 in contest....

Itama wrote: 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. Thanks. Lamenting the fact that my contestant days are over already since this is my first solved IMO 2/5... I thought it was a very beautiful problem, however. Hoping for some nice stuff tomorrow too!

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_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}$. Nice solution!!

Last year's P1 was also a sequence problem with "divisible by 3" being the answer.

samoha wrote: Last year's P1 was also a sequence problem with "divisible by 3" being the answer. Indeed

We claim that the answer is all multiples of 3. We see that this is achieved by repeating strings of $2, -1, -1$. Note \[a_{i+2}i_{i-1}-a_{i-1} = a_{i-1}a_{i}a_{i+1} = a_{i+1}^2-a_{i+1}\]Adding these up cyclically gives \[\sum{a_{i}^2} = \sum{a_{i}a_{i+3}}\]Note that if we square this, we get \begin{align*} \sum{a_{i}^2}^2 = \sum{a_{i}a_{i+3}}^2 &\implies \sum{a_{i}^2}\sum{a_{i}^2} = \sum{a_{i}a_{i+3}}^2 \\ &\implies \sum{a_{i}^2}\sum{a_{i+3}^2} = \sum{a_{i}a_{i+3}}^2 \\ &\implies \exists t \mid a_{i} = ta_{i+3} \end{align*}If $3 \nmid n$, then $a_{i} = t^{k}a_{i} \implies a_{i} = 0$ or $a_{i} = a_{i+1}$, impossible. If $3 \mid n$, then the sequence cycles between strings of 3, notably $2, -1, -1$, and we're done.

NO_SQUARES wrote: Ywgh1 wrote: Claim 4: We must have the sequences signs being (+,-,-) periodically. pf: By claim 3 we know that after a positive there must be a negative term. but this forces the term after to be negative too Why can't be $a_ia_{i+1}+1>0$ if $a_i>0, a_{i+1}<0$? Numbers in condition are reals, not integers. thanks for pointing out I actually have another missing Will edit right away thanks

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

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.

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.

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.

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)$.

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.

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.

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.

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.

Subjective Rating (MOHs)

$ $

Attachments:

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.

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}\]

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.