Un problema de calculadora

Question

Otro reto:
Una calculadora tiene dos teclas especiales:
*La tecla A transforma un numero x en el numero 2x.
**La tecla B transforma un numero x en el numero 2x − 1.

¿Es cierto que, si se empieza con cualquier entero positivo, es posible apretar una secuencia de teclas especiales de tal forma que se obtenga al final la quinta potencia de un numero entero?

Por simple inspeccion uno se da cuenta que con las potencias de 2 mayores que 1 se puede obtener una quinta potencia usando la tecla A , ¿pero sera posible con otros numeros?

Comments

Empezando con 3: BBBBAABABBAAB = $7^5$. Esto es basicamente porque $2^k x - 2^k < 7^5 \leq 2^k x$ para $k=13$. De hecho, cualquier numero entre $2^k x - 2^k $ y $2^k x$ se puede obtener con una secuencia de teclas A y B.

Answer 1

Como dijo carlos, cualquier número en $(2^k(x-1), 2^kx]$ se puede obtener a partir de $x$ con una secuencia de teclas A y B, a saber, para obtener $2^k x - m$ (con $0 \le m < 2^k$) escribe $m$ en base dos, digamos $m = d_0 + 2d_1 + \cdots 2^{k-1} d_{k-1}$ (donde cada $d_i$ es cero o uno) y presiona la secuencia $T_{k-1} T_{k-2} \ldots T_0$ donde $T_i$ es la tecla A si $d_i = 0$ y es B si $d_i = 1$.

Ahora lo que queremos saber es si para cualquier $x$ existe alguna $k$ tal que hay una quinta potencia en $(2^k(x-1) , 2^k x]$. Pero $2^k (x-1) < m^5 \le 2^k x$ es equivalente a $2^{k/5} \sqrt[5]{x-1} < m \le 2^{k/5} \sqrt[5]{x}$ y como $\lim_{k\to\infty} 2^{k/5} \left(\sqrt[5]{x} - \sqrt[5]{x-1} \right) = \infty$, es obvio que cualquier $k$ suficientemente grande funciona.