Las Claves del problema

Question

Otro reto: Una calculadora tiene dos teclas especiales:

• Una clave que transforma un número x en el número de 2x.
• B clave transforma un número x en el número 2x - 1.

Es cierto que si puedes empezar con cualquier número entero positivo, es posible pulsar una tecla especial de la secuencia de tal manera como para obtener, finalmente, la quinta potencia de un número entero?

Por simple inspección se da uno cuenta de que las potencias de 2 mayor que 1, se puede llegar a la quinta potencia el uso de la tecla, pero será posible con otros números?

Answer 1

En este post, voy a interpretar el problema de la siguiente manera. Para cualquier entero positivo $n$, si empezamos con $n$ y realizar alguna secuencia de pulsaciones de teclas $A,B$, vamos a llegar a la quinta potencia de un número entero positivo. Cabe señalar que Chris Culter resuelto la interpretación de los cuantificadores invertido en otra respuesta.

Mantenga $n$ fijo en todo.

Lema 1. Para cualquier entero no negativo $k$ y cualquier entero $x$ en el intervalo de $[2^kn-2^k+1,2^kn]$, hay una secuencia de pulsaciones de teclas que se traduce en $x$ a partir de a $n$.
Prueba. Nos introducirá en $k$. Si $k=0$, el intervalo es sólo $\{n\}$ consta de sólo nuestro valor inicial. Por lo tanto, asumen $k>0$ y el inductivo hipótesis para $k-1$. $$2^kn-2^k+1\le x\le 2^kn\implies 2^{k-1}n-2^{k-1}+1\le\left\lceil\frac x2\right\rceil\le 2^{k-1}n$$This means $\a la izquierda\lceil\frac x2\right\rceil$ is the result of a sequence of keystrokes starting at $n$. If $x$ is even, $2\left\lceil\frac x2\right\rceil=2\frac x2=x$. If $x$ is odd, $2\left\lceil\frac x2\right\rceil-1=\frac{2(x+1)}2-1=x$.$espacio \\square$

Lema 2. Existe un entero $k\ge 0$ tal que para cualquier entero positivo $x$ satisfactorio $x^5\le 2^kn$, $$(x+1)^5-x^5\le 2^k-1.$$
Prueba. Primera $(x+1)^5-x^5=1+5x+10x^2+10x^3+5x^4\le 31x^4\le 31\left(\sqrt[5]{2^kn}\right)^4$. Desde $31x^4$ es un número entero, sólo necesitamos encontrar $k$ suficientemente grande como para que $\lfloor31(2^kn)^{4/5}\rfloor\le 2^k-1$ mantiene.

Sin embargo, si $k>5\log_2(31n^{4/5})$, luego $$31(2^kn)^{4/5}=2^{(4/5)k}(31n^{4/5})<2^{(4/5)k+(1/5)k}=2^k,$$ using $2^{(1/5)k}>31n^{4/5}$. It follows that $$(x+1)^5-x^5\le\lfloor31(2^kn)^{4/5}\rfloor\le 2^k-1.\space\square$$

Teorema. No es un entero positivo $x$ tal que $x^5$ puede ser alcanzado por una secuencia de pulsaciones de teclas de partida en $n$.
Prueba. Deje $k$ ser como en el Lema 2. Basta, por el Lema 1, demostrar que no está a la quinta potencia en el intervalo de $[2^kn-2^k+1,2^kn]$. Hay una mayor entero $x$ tal que $x^5<2^kn-2^k+1$. A continuación, $(x+1)^5-x^5\le2^k-1$, por lo que $$(x+1)^5=(x+1)^5-x^5+x^5<2^k-1+2^kn-2^k+1=2^kn.$$ Hence, $(x+1)^5$ must be within the interval $[2^kn-2k+1,2^kn]$.$espacio\\square$

Answer 2

En primer lugar, podemos caracterizar el espacio que estamos trabajando.

Deje $X_n$ denota el conjunto de $n$-tuplas con las entradas en $\{A,B\}$ y considerar los conjuntos de $$G_k=\bigcup_{j=1}^k\left\{\left(\prod_{i=1}^jx_k\right)m:x\in X_n\right\}\subseteq \mathbb{Z}[m]$$ Ahora vamos a formar $\bar G=\bigcup_{k=1}^\infty G_k$.

La reclamación. $$\bar G = \bigcup_j\left\{2^jm-2^{j}+1,\ldots, 2^jm\right\}.$$

Prueba. Vamos a probar esto por inducción. Escribir $L_j=\left\{2^jm-i:i=\{0,\ldots,2^j-1\}\right\}$. El caso base es trivial. Ahora, $$\begin{eqnarray*}A L_n&=&\left\{2\times (2^nm-i):i\in\{0,\ldots,2^n-1\}\right\}\\&=&\left\{2^{n+1}m-i:i\in\{0,2,\ldots,2^{n+1}-2\}\right\}\end{eqnarray*}$$ y $$\begin{eqnarray*}B L_n&=&AL_n-1\\&=&\left\{2^{n+1}m-i:i\in\{1,3,\ldots,2^{n+1}-1\}\right\}\end{eqnarray*}$$ por lo $$L_{n+1}=AL_n\cup BL_n.$$

Si definimos $\varphi_n:\bar G \rightarrow \mathbb{Z}$$\varphi_n(f)=f(n)$$g(x)=x^5$, queremos demostrar que, para cada $n\in \mathbb{N}$, $$\varphi_n[\bar G]\cap g[\mathbb{Z}]\ne\emptyset.$$ Nuestra estrategia será la de encontrar una lo suficientemente grande como $j$, de modo que $\varphi_n[L_j]$ es lo suficientemente grande, que debe contener una quinta parte de la raíz (de modo que $g^{-1}(x)$ es un número entero para algunos $x\in L_j$). Por supuesto, podemos encontrar un número tan largo como $$f_m(j)= g^{-1}\left(2^jm\right)-g^{-1}\left(2^j(m-1)+1\right)\geq 1$$ que, por algunos relativamente desordenado cálculos, es cierto cuando se $g(x)=x^5$. Me he dejado a $g$ arbitrarias para hacer el punto de que no sólo la quinta parte de las raíces, pero en realidad las raíces suficientes, así como cualquier aumento de la función polinomial.

Answer 3

Si la pregunta es de la forma sugerida por Scaramouche del comentario, la respuesta es no. Ambas claves son permutaciones en $\mathbb Z/9$, por lo que cualquier secuencia de teclas es también una permutación, y por lo tanto hay algunos que comienzan $x$ que se envía a $3$. Pero $3$ no está a la quinta potencia en $\mathbb Z/9$.