# sequence generated with polynomials

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.

• Just making sure: do both components of the second generated pair have $x_k$ as the argument? – Alexander Burstein Jan 5 '18 at 6:01
• I believe the answer is that n is cute iff n=3. I also believe this is the wrong forum for your question. Gerhard "Hint: What's Cute Minus One?" Paseman, 2018.01.04. – Gerhard Paseman Jan 5 '18 at 7:58
• Here is another cute hint: the arguments don't matter. Thus the first version of the post has almost the same answer as this version. Gerhard "That's Enough Hints For Today" Paseman, 2018.01.05. – Gerhard Paseman Jan 5 '18 at 8:09

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