sequence generated with polynomials

Question

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.

Answer 1

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