Below is an old olympiad problem, that turned out to be notoriously hard, that we couldn't solve it. If anyone has a solution for it, I'd be grateful.


Let $P(x)=x+1$, and $Q(x)=x^2+1$. We consider all sequences of pairs, namely, $\{(x\_k,y\_k)\}\_{k=1}^\infty$ such that, we have the following rule to generate: $(x\_1,y\_1)=(1,3)$, and for every $k$, $(x\_{k+1},y\_{k+1})$ is,
$$
\text{either } (P(x\_k),Q(y\_k)) \text{ or } (Q(x\_k),P(y\_k)).
$$
Call a positive integer $n$ as cute, if there exists at least one such sequence, on which, $x\_n=y\_n$. Find all cute $n$'s.



sequence generated with polynomials
Assume that you have found a sequence with $x\_n=y\_n$ for some $n$. Call $x=\sqrt{x\_n-1}$ Then the previous couple in your sequence was $(x^2, x)$. Now $x^2$ cannot be $Q(\text{some integer})$ since it is a square (unless $x=1$ which is not possible as $(1, 1)$ is unreachable from $(3, 1)$). In fact you have to subtract $1$ from $x^2$ at least $\underline{\smash{2x-2}}$ times before you reach an integer that can possibly result from applying $Q$ to an integer: $$x^2-(2x-2)=(x-1)^2+1$$
In the meantime, what happens to poor $x$ (the other coordinate) is that you apply the map $Q^{-1}:t\mapsto \sqrt{t-1}$, also $2x-2$ times.


No integer $x$ greater than $1$ can survive the application of this map $2x-2$ times and stay a positive number all along. Hence the only way you can have a solution is when you reach $(3,1)$ *before* you're done with the $2n-2$ steps. Remember that $x^2$ was initially the greater coordinate, and it is the one getting down $1$ by $1$ so it stays greater all along, which means it is the one ending up at $3$. So you have to solve $$x^2-k=3\qquad Q^{-k}(x)=1$$


where it is easy to see that there are no solutions larger than $x\_3=y\_3=5$.


