23 votos

Saltos en los números enteros

Consideremos digrafos infinitos cuyos vértices son los enteros $\mathbb Z$ con la propiedad de que hay exactamente dos arcos que salen de cada vértice. (No hay ninguna restricción sobre el número de arcos entrantes).

La pregunta: ¿existe un dígrafo tal que para $m,n\in\mathbb Z$ con $m<n$ existe un camino dirigido desde $m$ a $n$ de longitud $O(\log(n-m))$ ?

Este problema es una abstracción del que se plantea en las estructuras de datos (imagine una lista enlazada con dos enlaces por nodo). Hace años confiaba en haberlo resuelto, pero no encuentro mis apuntes y ahora mismo sólo veo $O(\log(n-m)^2)$ .

Además de la existencia, estaría bien que hubiera un algoritmo eficaz para seguir el camino, es decir, dado que estás en $m$ puede averiguar rápidamente cómo llegar a $n$ sur $O(\log(n-m))$ pasos. Defina "rápidamente" como quiera.

27voto

Noam D. Elkies Puntos 40187

Sí, ese grafo dirigido existe, con un camino "rápidamente" computable de longitud $O(\log|n-m|)$ de $m$ a $n$ para cualquier número entero distinto $m,n$ .

Primero construiré un dígrafo con esta propiedad pero en el que cada vértice tiene como máximo un grado de salida $8$ y luego mostrar cómo obtener a partir de él un dígrafo de grado exterior $2$ .

Denote por $v(x)$ el $2$ -valoracion adica del entero $x$ que es el único entero $e \geq 0$ tal que $x/2^e$ es un número entero impar; convencionalmente $v(0) = \infty$ .

Las aristas del gráfico que emanan de $x$ serán los siguientes. Si $x$ tiene valoración $e>0$ entonces $$ x \rightarrow x \pm 1, \phantom+ x \pm 2^{e-1}, \phantom+ x \pm 2^e, \phantom+ x \pm 3\cdot 2^e. $$ Si $x$ es impar, omitir $x \pm 2^{e-1}$ así que $x$ va sólo a $x \pm 1$ y $x\pm 3$ . Si $x=0$ entonces $x\mapsto \pm 1$ sólo.

Entonces:

(i) Para cada $e \geq 0$ los enteros de valoración $e$ constituyen una progresión aritmética de diferencia común $2^{e+1}$ . Podemos obtener de tales $x$ a $x \pm 2^{e+1}$ en dos pasos: si $e=0$ a continuación, sumar o restar $1$ dos veces; si $e>0$ a continuación, sumar o restar $2^{e-1}$ y luego $3 \cdot 2^{e-1}$ .

(ii) Si $v(x) = e$ y $|n-m| \leq 2^e$ podemos obtener de $m$ a $n$ en un máximo de $2 \phantom. \log_2 |n-m| + 1$ pasos. En efecto, si $|n-m| = 2^e$ basta con un paso, así que supongamos $|n-m| < 2^e$ y luego $|n-m| \in [2^d, 2^{d+1})$ con $d < e$ . Por simetría podemos suponer $n>m$ . Entonces $$ m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d $$ en $d+1$ pasos, y luego en otro $d - v(n)$ pasos que alcanzamos $n$ escribiendo $$ n = m + 2^d + 2^{d-1} \pm 2^{d-2} \pm 2^{d-3} \pm \cdots \pm 2^{d-v(n)}. $$

(iii) Si $v(m) = e < f$ y $n$ es el número entero de valoración exactamente $f$ que está más cerca de $m$ entonces podemos obtener de $m$ a $n$ sur $f-e$ pasos. En el $i$ -ésima etapa, añada $\pm 2^{e+i-1}$ o $\pm 3 \cdot 2^{e+i-1}$ para alcanzar un número de valoración exactamente $e+i$ ; hay dos opciones, así que coge la que esté más cerca de $n$ . La distancia a $n$ siempre queda por debajo de $2^f$ por lo que en el paso $f-e$ golpeamos $n$ .

(iv) Por último, supongamos $m$ es impar y $|n-m| \in [2^k, 2^{k+1})$ . Visite $n'$ de valoración $k$ tal que $|n-n'| \leq 2^k$ . Así $|m-n'| < 3 \cdot 2^k$ . Por (iii), en $k$ pasos que obtenemos de $m$ a algunos $n_1$ tal que $|m-n_1| < 2^k$ y $v(n_1) = k$ . Así que $n_1=n'$ o $n_1 = n' \pm 2^{k+1}$ y en este último caso llegamos a $n'$ en otros dos pasos utilizando (i). Entonces, en un máximo de $2k+1$ más pasos alcanzamos $n$ utilizando (ii).

Hemos terminado, en un total de $3 \phantom. \log_2 |n-m| + O(1)$ pasos, porque si $m$ no es impar entonces podemos utilizar nuestro primer paso para pasar al número impar $m \pm 1$ más cerca de $n$ .

Ahora para pasar de grado $8$ hasta $2$ para cada $x \in {\bf Z}$ elija $f_i(x)$ para $i=0,1,2,\ldots,7$ para que $\{f_0(x),f_1(x),f_2(x),\ldots,f_7(x)\}$ es el conjunto de enteros alcanzables desde $x$ (con repeticiones si $x$ es impar o cero). Definir un nuevo gráfico de grado de salida $2$ como sigue: escriba cada número entero como $8x+i$ para algunos $x \in \bf Z$ y $i\in\{0,1,2,\ldots,7\}$ y luego $8x+i \rightarrow 8f_i(x)$ y $8x+i \rightarrow 8x+i'$ donde $i'=0$ si $i=7$ y $i'=i+1$ de lo contrario. Es decir, dividimos $\bf Z$ dirigida $8$ -lo que consume sólo una arista saliente por entero y nos deja con $8$ más aristas por ciclo para asignarlas como queramos, lo que nos permite utilizar nuestro gráfico de grados de salida $8$ . Cada paso de nuestro algoritmo se expande entonces a lo sumo a $8$ porque puede que tengamos que tomar hasta $7$ pasos dando vueltas hasta llegar al $i$ para dar el siguiente paso en nuestro gráfico original, y al final puede que aún tengamos que gastar un $7$ pasos para alcanzar el objetivo $n$ dentro de su ciclo. Pero eso sigue siendo como mucho $24 \phantom. \log_2 |n-m| + O(1)$ pasos, y aún con un algoritmo explícito y "rápido".

[ EDITAR podemos reducir $3 \phantom. \log_2 |n-m| + O(1)$ a $\frac52 \log_2 |n-m| + O(1)$ comprimiendo $$m \rightarrow m + 1 \rightarrow m + 2 \rightarrow m+4 \rightarrow \cdots \rightarrow m+2^d$$ a $$m \rightarrow m + 1 \rightarrow m + 4 \rightarrow m+16 \rightarrow \cdots \rightarrow m+2^d,$$ y probablemente haya otro múltiplo de $\log_2|n-m|$ que se guardará permutando $f_0(x),f_1(x),f_2(x),\ldots,f_7(x)$ para reducir el número de pasos que hay que dar dentro de $8$ -ciclos.]

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X