¿Después de cuántos pasos pueden composiciones de $x\mapsto x+1$ y $x\mapsto x^2+1$ producen el mismo resultado a partir de $1$ y $3$?

Question

Este problema es de un turco concurso:

Deje $P(x)=x+1$$Q(x)=x^2+1$.

Considerar todas las secuencias $(x_k,y_k)$ tal que $(x_1,y_1)=(1,3)$ y
$(x_{k+1},y_{k+1})$ es $(P(x_k),Q(y_k))$ o $(Q(x_k),P(y_k))$.

Encontrar todos los enteros positivos $n$ tal que $x_n=y_n$ mantiene en al menos una de estas secuencias.

Claramente, $n=3$ es una posibilidad ($(x_2,y_2)=(2,4)$, $(x_3,y_3)=(5,5)$) y parece ser la única, pero no sé cómo proceder en el caso general.

Se agradece cualquier ayuda, gracias.

Answer 1

Deje $f(x)=x^2+1$. Si $x_k=y_k$$k\ge4$, $x_{k-1}=y_{k-1}^2$ o $y_{k-1}=x_{k-1}^2$. Solo consideraremos $x_{k-1}=y_{k-1}^2$ y deje $(x_1,y_1)$ $(1,3)$ o $(3,1)$ tanto sea posible.

Vamos a demostrar a través de la inducción $$x_{k-t-1}+t=f^t(y_{k-t-1})^2\tag{1}$$ for all $t\le k-2$. Para $t=1$, de $x_{k-1}=y_{k-1}^2$ $$x_{k-2}+1=(y_{k-2}^2+1)^2=f(y_{k-2})^2\text{ or }x_{k-2}^2+1=(y_{k-2}+1)^2$$ The second case is impossible since $y_{k-2}+1\ge2$ so the first case must be true. So $(1)$ is true for $t=1$.

Ahora Suponga $(1)$ cierto para $t=u$ donde $1\le u\le k-3$. Debemos tener $$x_{k-u-2}+u+1=f^{u+1}(y_{k-u-2})^2\text{ or }x_{k-u-2}^2+u+1=f^u(y_{k-u-2}+1)^2$$ First consider the second case. Since $a^2-b^2\ge 2a-1$ for all $a>b$, we have$$u+1=f^u(y_{k-u-2}+1)^2-x_{u-k-2}^2\ge2f^u(y_{k-u-2}+1)-1\ge2f^u(2)-1>2(2+u)-1$$ which is a contradiction. So the second case must be true which means $(1)$ is also true for $t=u+1$.

Por lo $(1)$ es cierto para $t=k-2$. Lo que significa que $x_1+k-2=f^{k-2}(y_1)^2$. Pero esto es imposible, ya que $$k+1\ge x_1+k-2=f^{k-2}(y_1)^2\ge f^{k-2}(1)^2=f^{k-4}(5)^2\ge(5+(k-4))^2>k+1$$ Por lo tanto no podemos tener a $k\ge 4$. Para $k\le 3$, podemos comprobar fácilmente que $k=3$ sólo es posible con la $(x_2,y_2)=(2,4),(x_3,y_3)=(5,5)$.