Generación de números Prueba

Question

Podemos realizar las siguientes acciones: multiplicar por $10$ (añadir $0$ al final del número) , multiplique por $10$ y añadir $4$ (añadir $4$ al final del número) y dividir por $2$ . Necesito demostrar que podemos obtener cada número natural de $4$ utilizando estas acciones.

¿Es más fácil demostrar que a partir de cualquier número puedo obtener $4$ multiplicándolo $2$ dividiendo por $10$ y extraer su última $4$ ¿o es el mismo problema?

Answer 1

Este es un problema más complicado de lo que esperaba, así que esta es sólo una respuesta parcial por ahora.

Trabajando hacia atrás, está claro que se puede llegar desde cualquier número que termine en $0$ o un $4$ a un número más pequeño en un solo paso, simplemente borrando el último dígito (es decir, dividiendo por $10$ , en el primer caso, o restar $4$ y luego dividir por $10$ en el segundo caso). Del mismo modo, si $N$ termina en un $2$ , $5$ o $7$ se llega a un número menor en dos pasos: primero se multiplica por $2$ y luego eliminar el resultante $0$ o $4$ en el dígito uno. Del mismo modo, si $N$ termina en un $1$ o un $6$ tres pasos serán suficientes para llegar a un número menor, mientras que si termina en un $3$ o $8$ En el caso de que el número sea menor en cuatro pasos, es decir, tres duplicaciones seguidas de una reducción de al menos un factor de $10$ .

El punto de fricción es si $N$ termina en un $9$ . En ese caso se necesita cuatro dobles antes de poder eliminar un $4$ pero en ese punto te quedas con un número que es más grande que con lo que empezó. Por ejemplo, veamos $N=49$ :

$$49\to98\to196\to392\to784\to78$$

Incluso continuando para otra ronda nos deja algo más grande que $49$ :

$$78\to156\to312\to624\to62$$

Sólo dando una vuelta más terminamos con algo más pequeño que $49$ :

$$62\to124\to12$$

Parece que nunca debería tomar más de tres rondas para llegar de $N$ a un número menor que $N$ (momento en el que se puede decir "fuerte inducción" y dar por terminado el asunto), pero habrá que mirar más de cerca de lo que lo he hecho aquí para estar seguros. El problema tiene bastante del sabor del clásico $3x+1$ problema para estar seguro de que no hay ninguna laguna legal. Por otro lado, tal vez haya algún argumento elemental que estoy pasando por alto. Si tengo la oportunidad, le daré más vueltas al problema, pero me encantaría que alguien publicara una respuesta completa.

Actualización (7 de abril de 2016): Me equivoqué al afirmar que nunca se necesitan más de tres rondas para llegar a un número menor (donde cada "ronda" termina en la eliminación de los restos $4$ y $0$ 's). Aquí hay un ejemplo que toma cuatro rondas:

$$749\to1498\to2996\to5992\to11984\to1198\\ 1198\to2396\to4792\to9584\to958\\ 958\to1916\to3832\to7664\to766\\ 766\to1532\to3064\to306$$