Menos pasos para llegar $200$ de $1$ utilizando sólo $+1$ y $×2$

Question

Este es un problema del AMC 8 (concurso de matemáticas):

Una determinada calculadora sólo tiene dos teclas $[+1]$ y $[\times 2]$ . Al pulsar una de las teclas, la calculadora muestra automáticamente el resultado. Por ejemplo, si la calculadora muestra originalmente " $9$ " y presionaste $[+1]$ , se mostraría " $10$ ". Si a continuación se pulsa $[\times 2]$ , se mostraría " $20$ ". A partir de la indicación " $1$ ", ¿cuál es el menor número de pulsaciones que necesitarías para llegar a " $200$ "?

Intuitivamente trabajé desde $200$ dividiendo por $2$ hasta llegar a un número impar, restando $1$ cuando lo hice, etc. para llegar a la respuesta correcta de $9$ pasos.

Sin embargo, no consigo convencerme sin lugar a dudas de que es la solución óptima. En otras palabras, no puedo demostrarlo matemáticamente. Lo mejor que se me ocurre es que más allá del primer paso de $1$ a $2$ , multiplicación por $2$ siempre va a dar un paso mayor que la suma por $1$ y por lo tanto debería tomar tantos $[\times 2]$ pasos como pueda. Sin embargo, esto no parece lo suficientemente riguroso.

EDIT: Para que quede claro, pido una prueba o al menos una explicación más rigurosa de por qué esta es la solución óptima.

Answer 1

Mira lo que las operaciones $[+1]$ y $[\times 2]$ hacer a la expansión binaria de un número:

• $[\times 2]$ añade un $0$ y aumenta la longitud en uno, dejando el número total de $1$ no ha cambiado;
• si el último dígito es $0$ entonces $[+1]$ aumenta el número de $1$ por uno, pero no cambia la longitud;
• si el último dígito es $1$ entonces $[+1]$ no aumenta el número total de $1$ (de hecho puede disminuirla), y no aumenta la longitud total en más de $1$ .

Por lo tanto, con una sola pulsación de tecla:

• puede aumentar la longitud en uno, pero esto no aumentará el número de $1$ 's;
• puede aumentar el número de $1$ 's por uno, pero esto no aumentará la longitud.

La expansión binaria de $200$ es $200_{10}=11001000_2$ . Esto tiene tres $1$ y una longitud de ocho. A partir de $1$ debemos aumentar la longitud en siete, y aumentar el número de $1$ por dos. Así que esto requiere al menos nueve pasos.

Answer 2

Puede proceder por inducción en $n$ , demostrando que la forma más rápida de alcanzar cualquier número par $2n$ implica la duplicación en el último paso, lo que es claramente cierto para el caso base $n=1$ (donde la duplicación y la adición $1$ tener un tomate-tomahto relación).

Ahora bien, si el último paso para llegar $2n+2$ no está duplicando, sólo puede estar añadiendo $1$ de $2n+1$ . Pero $2n+1$ sólo se puede alcanzar añadiendo $1$ de $2n$ En ese momento la hipótesis inductiva dice que el siguiente número anterior era $n$ . Pero se puede obtener de $n$ a $2n+2$ más rápidamente en dos pasos: añadir $1$ y luego el doble. Así que el último paso en la ruta más rápida para $2n+2$ se duplica de $n+1$ .

Answer 3

Ajuste de la pantalla en base binaria, $[\times2]$ inserta un $0$ a la derecha y $[+1]$ incrementos; si el dígito más a la derecha es un cero, simplemente lo convierte en un $1$ .

Con estas reglas se construye una serie de $o$ y $z$ ceros en $o-1+z$ pulsaciones de teclas, a partir de $1$ . Esto parece estar cerca de lo óptimo.

Answer 4

Trabajando hacia atrás, utilice el diagrama de árbol y detenga las ramas retrasadas (por ejemplo, si $\color{red}{99}$ al paso $3$ lleva a $1$ , entonces se necesita una operación más que $\color{red}{99}$ al paso $2$ ):

$\hspace{3cm}$

Answer 5

Voy a hacer un intento

Desde $200=2^7+2^6+2^3$ necesitará al menos $8$ pasos para llegar a $200$ (ya que partimos de $1$ y obtenemos un número de la forma $2^a+...+2^l$ ) por lo que queda por demostrar que $8$ los pasos no son suficientes.

Tal vez usted podría tratar de mostrar que si hubiera una solución con $8$ pasos, entonces sólo contendría una $+1$ lo que contradice el hecho de que en $200=2^7+2^6+2^3$ tenemos dos $+$