se mueve en una cuadrícula con números enteros condición

Question

supongo que usted es una pulga saltando en una cuadrícula (similar a $\mathbb{Z}^2$). Usted puede hacer cualquier salto que definir un número entero distancia, sino que además ha de cambiar tanto las coordenadas (por ejemplo, los movimientos (3,4) o (5,12) están permitidas, pero no en (1;0)).

La primera pregunta es para probar que en un número finito de salta, se puede llegar a cualquier elemento de $\mathbb{Z}^2$. Esta es la parte fácil y deja como ejercicio para el lector :)

Ahora, usted ha hecho a esta parte fácil, y usted sabe que usted puede llegar a (1;0) en 3 saltos, lo que significa que cualquier punto de coordenadas (a;b) es accesible en la mayoría de los 3(|a|+|b|) se mueve. Por supuesto, esta obligado es terrible. Pero aquí viene la dificultad real : es el número de movimientos necesarios para llegar a cualquier punto uniformemente acotada ? O, al menos, se puede hacer mejor que O(|n|) ? (decir que n es max (|a|,|b|), por ejemplo, no cambia nada en lo que a nosotros sólo estudiar lo que sucede asintóticamente).

Hasta ahora, supongo que uno puede utilizar algún algoritmo de Euclides truco para obtener algo en O(ln(|n|)), pero no tengo ninguna idea mejor. Es este problema (bien)-conocido ? Estudió en algún lugar ? Gracias de antemano por cualquier comentario ;)

Answer 1

Aquí es un argumento que demuestra que siempre podemos ir de $(0,0)$ $(a,b)$en tres saltos. Este es el mejor posible, ya que puede ir desde la $(0,0)$ $(0,1)$en dos saltos. (Prueba: por la desigualdad de triángulo, la longitud de los saltos difieren en menos de $1$. Pero sólo pueden ser iguales si nos salta de$(0,0)$$(x,\frac12)$%#%, que no está en la red.)

En primer lugar, aquí es un esquema mediante el cual nos puede a veces ir de $(0,1)$ $(0,0)$en dos saltos. Primero, salto de$(a,b)$$(0,0)$. A continuación, saltar de $(3x,4x)$$(3x,4x)$. Vamos a resolver para el $(3x+4y,4x+3y)$ $x$ necesario para obtener a $y$ y ver que $(a,b)$$ Esto no es siempre válido, porque $$\begin{cases}3x+4y = a \\ 4x+3y =b\end{cases} \implies x = \frac{4b-3a}{7}, y = \frac{4a-3b}{7}.$ $x$ no son siempre números enteros. De hecho, son números enteros exactamente al $y$.

Así que en lugar de tratar de hacer estos saltos para ir de $a+b \equiv 0 \pmod 7$$(0,0)$, vamos a considerar los siete lugares de destino: $(a,b)$$(a + 7z, b + 24z)$. Como $0 \le z \le 6$ varía, la suma de $z$ rangos de todos los posibles valores de modulo $(a+7z)+(b+24z)$, por lo que uno de estos lugares de destino va a ser un punto de $7$$(a',b')$, lo que significa que puede obtener con dos saltos. Y $a'+b' \equiv 0 \pmod 7$ es un número entero distancia de $(a',b')$$25z$, por lo que podemos terminar con un tercer salto a $(a,b)$.

En resumen, se puede obtener de $(a,b)$ $(0,0)$en tres saltos: $(a,b)$$