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.

  • 1
    $\begingroup$ Just making sure: do both components of the second generated pair have $x_k$ as the argument? $\endgroup$ – Alexander Burstein Jan 5 '18 at 6:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 5 '18 at 7:58
  • $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ That's the idea, although it may be cleaner to say that from (1,x^2-k) one reaches (for some b greater than 2^{2^{k-1}}) (b,x^2) only through k applications of (Q,P), and thus k has to be small compared to x to reach (b,x^2) for b smaller than x^2. Gerhard "More Of A Guideline, Really" Paseman, 2018.01.05. $\endgroup$ – Gerhard Paseman Jan 6 '18 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.