En el $x + 1$ problema, ¿todo entero positivo $x$ finalmente llegar a $1$ ?

Question

Sé que los más famosos $3x + 1$ El problema sigue sin resolverse. Pero me parece que el similar $x + 1$ con la función

$$f(x) = \begin{cases} x/2 & \text{if } x \equiv 0 \pmod{2} \\ x + 1 & \text{if } x \equiv 1 \pmod{2}.\end{cases}$$

debería ser muy fácil demostrarlo sólo con mis modestos y azarosos conocimientos de matemáticas. Pero lo único que se me ocurre es "por supuesto que cada $x$ tiene que alcanzar $1$ , lo que claramente no es una prueba rigurosa.

¿Es esto fácil de probar, o es quizás tan difícil como el $3x + 1$ ¿Problema?

Answer 1

Esta cuestión no es demasiado difícil de resolver si nos fijamos en $f(f(x))$ . Tenemos $$f(f(x))=\left\{\begin{array} \displaystyle{\tfrac{x}{4}} &\text{ if }x\equiv0\pmod{4}\\ \tfrac{x}{2}+1&\text{ if }x\equiv2\pmod{4}\\ \tfrac{x}{2}+\tfrac{1}{2}&\text{ if }x\equiv1\pmod{2} \end{array}\right.$$ En particular, vemos que $f(f(x))<x$ si $x>3$ . Así que para todos $x>3$ al final llegaremos a un número entero que es como máximo $3$ . Entonces podemos terminar comprobando que $$f(2)=1\qquad\text{ and }\qquad f(f(f(3)))=1.$$ Así que cada número entero $x$ finalmente termina en $1$ . Un enfoque similar funciona si se sustituye $x+1$ por $ax+b$ con $a\leq2$ y cualquier $b>0$ aunque hay más números que comprobar a mano para los grandes $b$ .

Answer 2

La variante que has descrito no es difícil. Por ejemplo, se puede dar una prueba formal por inducción fuerte.

Este es el paso de la inducción. Supongamos que al final acabamos en $1$ si empezamos en cualquier número $u\lt k$ . Demostramos que terminamos en $1$ si empezamos en $k$ .

Si $k$ es uniforme, en un paso estamos por debajo de $k$ y hemos terminado.

Si $k$ es impar y mayor que $1$ , en dos pasos estamos en $\frac{k+1}{2}\lt k$ .