Viaje entre enteros - potencias de 2

Question

Nota del moderador: En el momento en que se publicó esta pregunta, era de un concurso en curso. El plazo correspondiente ya ha pasado.

Consideremos los números enteros. Sólo podemos viajar directamente entre dos enteros con una diferencia cuyo valor absoluto sea una potencia de 2 y cada vez que lo hacemos se llama un paso. La distancia $d$ entre dos enteros es el número mínimo de pasos necesarios para llegar de uno a otro. Sin embargo, hay que tener en cuenta que podemos viajar hacia atrás. Por ejemplo $d(2,17)$ es 2: $2+16=18 \rightarrow 18-1=17$ .

¿Cómo podemos demostrar que para cualquier número entero n, siempre tendremos algún $d(a,b)=n$ donde $b>a$ ?

---

Si sólo podemos dar pasos hacia adelante, sé que el número de 1s en la representación binaria de $b-a$ sería $d(a,b)$ . Sin embargo, podemos dar pasos hacia la izquierda en la recta numérica...

Answer 1

Es fácil ver que la función $s(n):=d(0,n)$ $\ (n\geq1)$ satisface la siguiente recursión: $$s(1)=1,\qquad s(2n)\ =\ s(n), \qquad s(2n+1)=\min\{s(n),s(n+1)\}+1 \ .$$ En particular $s(2)=s(4)=1$ , $s(3)=2$ . Considere ahora los números $$a_r:={1\over6}(4^r+2)\qquad (r\geq2)$$ satisfaciendo la recursión $$a_2=3,\qquad a_{r+1}=4 a_r-1\quad (r\geq2).$$ Los primeros son $3$ , $11$ , $43$ , $171$ . Afirmo que $$s(a_r-1)=s(a_r+1)=r-1,\quad s(a_r)=r\qquad (r\geq2)\ .$$ La afirmación es válida para $r=2$ . Supongamos que es cierto para $r$ . Entonces $$s(2a_r-1)=\min\{s(a_r),s(a_r-1)\}+1=r,\qquad s(2a_r)=r$$ y por lo tanto $$s(4a_r-2)=s(4a_r)=r,\quad s(4a_r-1)=\min\{s(2a_r),s(2a_r-1)\}+1=r+1\ .$$ La última línea puede leerse como $$s(a_{r+1}-1)=s(a_{r+1}+1)=r, \qquad s(a_{r+1})=r+1\ .$$

Answer 2

Presumiblemente te refieres a todos los números naturales $n$ no todos los enteros $n$ . Podemos simplificar las cosas tomando $a=0$ sin pérdida de generalidad y luego escribir $d(b):=d(0,b)$ . Además, basta con demostrar que por cada $n$ hay $b$ con $d(b)\ge n$ ya que eso significa que para todo $n$ hay números no localizables en $n$ pasos, y entonces se deduce por inducción que para todo $n$ hay números alcanzables en exactamente $n$ pasos, ya que en cada etapa de la inducción hay números adyacentes de los cuales uno es alcanzable en $n$ pasos y el otro no, y a este último se puede llegar en un $(n+1)$ -a etapa de $1$ .

Ahora represente los enteros en "infinito complemento a dos ", es decir, un entero no negativo se representa por su representación binaria y un entero negativo $k$ se representa invirtiendo la representación binaria de $-(k+1)$ , considerada como una cadena infinita hacia la izquierda con ceros a la izquierda. Esto pone a los enteros en biyección con el conjunto de todas las cadenas binarias infinitas hacia la izquierda con un número finito de transiciones entre $0$ y $1$ .

En esta representación, la adición de un entero positivo a un número funciona como se espera, llevándose a cabo hasta el tramo infinito de $0$ s o $1$ s se alcanza, y el $1$ s volteado a $0$ s por un acarreo.

Ahora, en cada paso, podemos añadir una potencia positiva de dos al número que hemos alcanzado, y luego podemos, opcionalmente, invertir su signo. (Esto equivale a sumar o restar potencias de dos en cada paso.) Como voltear el signo significa invertir la cadena y luego sumar $1$ , en cada paso podemos invertir la cadena y sumar una potencia de dos hasta dos veces.

Invertir la cadena no cambia el número de transiciones entre $0$ y $1$ . Si se añade una potencia de dos, aumenta el número de transiciones entre $0$ y $1$ por un máximo de $2$ . Así, en cada paso podemos aumentar el número de transiciones como máximo $4$ . Dado que existen enteros cuyas representaciones tienen un número arbitrario de transiciones, para cada $n$ hay números enteros que no podemos alcanzar en $n$ pasos.

Answer 3

Considere $ a(n) = \sum_0^n 2^{2i} $ . Entonces $ d(0,a(n)) = n + 1 $ .

Prueba: En primer lugar, observa que en cualquier serie mínima de pasos, sólo puedes utilizar cada potencia de 2 una vez como máximo. Si la sumas dos veces en cualquier punto, podrías obtener el mismo resultado sumando la siguiente potencia más alta una vez (y si esa se usara, iterativamente hasta la primera que no se usara), lo mismo para la resta, y obviamente sumarla una vez y restarla una vez se anularía por completo, llevando cada una al mismo resultado con menos pasos.

Además, podemos hacer los pasos en un orden arbitrario, así que podemos suponer que hacemos primero todas las sumas.

Consideremos la representación binaria de $ a(n) = 10101...1 $ con $ n+1 $ $1$ s. Un "paso" equivale a la adición o sustracción de una potencia de $ 2 $ y empezamos en $ 0 $ .

Empezamos con las sumas, por lo que podemos poner cualquier número de bits en $1$ , siendo cada uno de ellos un paso. Luego hacemos las substracciones, y aquellas en orden de magnitud, la más pequeña primero.

Cualquier sustracción de una potencia de $ 2 $ volteará todos los $0$ a $1$ comenzando en su posición y subiendo en importancia hasta el primer $1$ que luego se invierte en $0$ (nótese que esto está garantizado porque nuestro número objetivo es positivo y, por tanto, la suma de las potencias sumadas debe ser mayor que la suma de las potencias restadas).

Ahora considere los bits en $a(n)$ empezando por la significación más baja. Cada $01$ par en la suma final sólo puede ser resultado de una de estas tres situaciones:

1. Teniendo la potencia correspondiente al $1$ en los pasos de adición.

2. Al ser el resultado de $10$ y la sustracción de la potencia de $2$ correspondiente al $01$ par de bits o una potencia inferior de $2$ . Pero en ese caso, que $10$ debe resultar de la adición o sustracción de esa potencia de $2$ .

3. O, por último, como resultado de una sustracción de una potencia inferior de $2$ de $00$ . Pero en ese caso, el resultado de la sustracción habría sido $11$ y, por tanto, la potencia de dos correspondiente al $0$ en ese par también debe restarse.

En 2. y 3. hemos aprovechado el hecho de que sólo podemos utilizar cada potencia de $2$ una vez como máximo, por lo que una vez $1$ se produce en un punto, las substracciones desde abajo no pueden ir más allá (como $ \sum_{i \lt n} 2^i \lt 2^n $ ).

Por lo tanto, necesitamos al menos un paso para cada $01$ par y la afirmación está probada.

Además, cualquier número $ b $ con $ d(0,b) = n+1 $ debe tener al menos $ 2n $ dígitos: Supongamos que $ b $ tenía menos de $ 2n $ dígitos en representación binaria. Si $b$ contiene $n$ o menos 1s, hemos terminado. Y si hay al menos $n+1$ $1$ s y, por tanto, como máximo $ n-2 $ $0$ s, entonces tenemos un procedimiento para generar $ b $ en $n$ pasos: Comenzar con $2^{2n}-1$ en dos pasos que dan como resultado $1...1$ y, a continuación, en un $n-2$ restamos todas las potencias de $2$ que corresponden a un $0$ en la representación binaria de $b$ . Como $d(0,1011_b)=3$ muestra, hay números con sólo $2n$ dígitos, sin embargo, así que $a(n)$ no es óptima.

Answer 4

Pista: Si representas los enteros en binario, una forma de construir un número a partir de cero es sumar las potencias de $2$ que son de un solo bit en la representación. Como has demostrado, puede haber una forma más rápida. Mira a ver si puedes encontrar un conjunto de números en los que el $1$ están lo suficientemente lejos como para que esta sea la forma más rápida de llegar.

Answer 5

Creo que el argumento de joriki se puede simplificar un poco :

con $n$ pasos, suponiendo que no se hagan estupideces como usar el mismo poder de $2$ dos veces o más, el número de enteros que puede alcanzar utilizando $n$ potencia hasta $2^k$ es como máximo $2^n \binom{k}{n} = P_n(k)$ donde $P_n$ es un polinomio (de grado $n$ ). Mientras tanto, si puede alcanzar un número $x < 2^l$ en $n$ pasos, entonces no se pueden utilizar potencias de dos arbitrariamente altas : si se utiliza $2^k \ge 2^{l+n}$ entonces no puedes restarle suficientes potencias menores para llegar a $x$ .

El número de enteros en $]-2^l, 2^l[$ es $2^{l+1}-1$ que es exponencial en $l$ pero el número de los que puedes alcanzar en $n$ pasos es menor que $P_n(l+n) = Q_n(l)$ que es un polinomio de grado $n$ en $l$ . Por lo tanto, para $l$ lo suficientemente grande que necesariamente se perderá algunos de esos números, por lo que el número de pasos necesarios para llegar a todos los enteros es ilimitado.