Pregunta si la langosta puede saltar a cualquier punto entero del plano después de un número finito de saltos si: $1) N = 20 $ $2) N = 2017 $

Question

En el plano de coordenadas hay una langosta en la coordenada $(0,0)$ . Siendo N un número entero positivo dado, la langosta puede saltar del punto entero $A$ al punto entero B si la longitud $AB$ es igual a $N$ . Pregunta si la langosta puede saltar a cualquier punto entero del plano después de un número finito de saltos si:

$1) N = 20 $

$2) N = 2017 $

Esto es todo lo que hice:

$ 1)N=20$

Asumiendo que la langosta está en $A(x,y)$ y puede pasar a $B(p,q)$ entonces tenemos $\sqrt{(x-p)^2+(y-q)^2} = 20 $

$\Rightarrow (x-p)^2+(y-q)^2=400$

Como un cuadrado es un cuadrado perfecto, sólo deja $0$ o $1$ cuando se divide por $4$ y $4|400$ $\Rightarrow 2|(x-p)$ y $2|(y-q) $

$\Rightarrow $ Si la langosta parte de $(0,0)$ entonces sólo puede moverse hasta un máximo de todos los puntos $(a,b)$ tal que $a$ y $b$ son incluso

Así que la langosta no puede moverse a todos los puntos enteros del plano

$2)N=2017 $

Sólo tenemos que demostrar que la langosta puede saltar a los puntos $(0,-1)$ y $(0,1)$ después de un número finito de saltos

Tenemos un análisis de la tríada Pitago : $2017^2 = 1855^2+792^2$

Así que para ir al grano $(0,1)$ La langosta ha caminado $x_1$ pasos con valor $1855$ y $x_2$ pasos con valor $792$ en el eje horizontal, caminó $y_1$ pasos con valor $1855$ y $y_2$ pasos con valor $792$ en el eje vertical del sistema de coordenadas

$\Rightarrow 1855x_1 + 792x_2 = 0$ y $1855y_1 + 792 y_2 = 0$

Así que necesito demostrar si el otro sistema de ecuaciones no tiene solución o existe. Pero no tengo ni idea. Espero recibir ayuda de todos. Muchas gracias.

Answer 1

$2017$ es un primo de la forma $4k+1$ por lo que se puede representar como una suma de dos cuadrados de forma esencialmente única, es decir $\color{red}{792}^2+\color{green}{1855}^2$ . Combinando dos saltos adecuados podemos movernos por $\pm 2\cdot 792$ unidades o $\pm 2\cdot 1855$ unidades a lo largo de la dirección horizontal o vertical. Dado que $792$ y $1855$ son coprimos, por la identidad de Bézout podemos llegar a cualquier punto del plano de la forma $(2m,2n)$ , a través de $(0,0)\stackrel{\text{hor}}{\longrightarrow}(2m,0)\stackrel{\text{vert}}{\longrightarrow}(2m,2n)$ . Con un salto adicional podemos alcanzar cualquier punto del plano de la forma $(2m+1,2n)$ o $(2m,2n+1)$ . Con un salto adicional podemos alcanzar cualquier punto del plano de la forma $(2m+1,2n+1)$ También.

También podemos utilizar un hecho de la teoría de grafos: en cualquier tablero de ajedrez de casillas suficientemente grande existe un recorrido cerrado de caballos (véase Schwenk ). Los caballos estándar se mueven a través de $(\pm 2,\pm 1)$ o $(\pm 1,\pm 2)$ mientras que nuestro épico caballero se mueve a través de $(\pm 1855,\pm 792)$ o $(\pm 792, \pm 1855)$ pero como $\gcd(792,1855)=1$ y $1855+792$ es impar esto no afecta a la declaración.

Answer 2

$2017,1855,792$ son coprimos y de diferentes paridades por lo que la respuesta a (2) va a ser sí

Por ejemplo,

• si se empieza en $(0,0)$ , dar un paso $(+1855,+792)$ y otro $(-1855,+792)$ terminas en $(0,1584)$ que es coprima de $2017$ .

• Así que repitiendo esto muchas veces y luego dando muchos pasos de $(0,-2017)$ , se puede llegar a $(0,1649\times 1584 - 1295 \times 207)=(0,1)$ ,

• y luego se puede llegar a cualquier otro punto mediante al menos combinaciones de éste y sus rotaciones (y probablemente más rápido por otras rutas).