Dado un $N\times N$ "ajedrez" de la junta (Deje $N = 10^{100}$) y un caballero en $(0,0)$.
Puede que el caballero ve a la posición $(x, y)$ con saltar $[a, b]$ se mueve ?
saltar $[a, b]$ media: el caballero de la en $(x,y)$ puede mover a $(x \pm a, y \pm b),\ (x \mp a, y \pm b), \ (x \pm b, y \pm a) \text{ or}\ (x \mp b, y \pm a)$
¿Puedo usar Un* algoritmo de búsqueda para resolver este problema ?
Puedo solucionarlo sin necesidad de un ordenador ?
He aquí una prueba de contorno para el específico subcase de si el caballo puede llegar a todas las posiciones; el resto debe ser un ejercicio fácil. Primero de todo, (como se señaló en los comentarios) el caballero puede llegar a todas partes iff puede obtener de $(0, 0)$$(1, 0)$: obviamente, si se puede llegar a todas las plazas que a continuación, se puede llegar a cualquier cuadrado. Por el contrario, en caso de llegar a $(1, 0)$, por simetría se puede llegar a $(0, 1)$ y, a continuación, por componer el movimiento de las secuencias de $m$ $n$ veces respectivamente, entonces se puede obtener a $(m, n)$ cualquier $m$$n$.
Ahora, tenga en cuenta que se puede restringir a la mitad de los movimientos disponibles si estamos dispuestos a hablar de ambos positivos y negativos mover cargos; nunca debemos mueve de la forma $(x, y)\to (x+a, y+b)$ $(x, y)\to (x-a, y-b)$ en la misma secuencia (desde que se podría llegar al mismo lugar por la omisión de ambos movimientos), por lo que podemos hablar de $\alpha (+a, +b)$ se mueve con la salvedad de que los $\alpha$ puede ser negativo. Para la concreción' bien, vamos a limitar a las cuatro clases de movimientos $(\pm a, +b)$$(\pm b, +a)$, y el uso de las variables $\alpha_+$, $\alpha_-$, $\beta_+$, $\beta_-$ para el número de movimientos de los cuatro tipos. A continuación, un movimiento de la secuencia para llegar a $(1, 0)$ debemos tener $a(\alpha_+-\alpha_-)+b(\beta_+-\beta_-) = 1$ y simultáneamente $b(\alpha_++\alpha_-)+a(\beta_++\beta_-) = 0$. Ahora, la última ecuación se puede resolver por $\alpha_++\alpha_-=a$, $\beta_++\beta_-=-b$, y si $\gcd(a,b)=1$ (y sólo entonces), a continuación, podemos encontrar $c, d$ tal que $ac+bd=1$.
A partir de estos valores, sin embargo, podemos backsolve para$\alpha_\pm$$\beta_\pm$: $\alpha_++\alpha_- = a$ $\alpha_+-\alpha_-=c$ obtenemos $\alpha_+ = \frac12(a+c)$$\alpha_-=\frac12(a-c)$, y, a continuación, del mismo modo $\beta_+ = \frac12(-b+d)$$\beta_- = \frac12(-b-d)$.
Además, desde el $\gcd(a,b)=1$, entonces al menos uno de $a,b$ es impar; vamos a decir que $a$ es siempre impar. Ahora, mediante la adición de $b$ $c$y restando $a$ $d$ si es necesario, siempre podemos optar $c$ impar y $d$, incluso en $ac+bd=1$; si $a$ es impar y $b$ es incluso entonces este es el final de la historia, desde entonces $\alpha_\pm=\frac12(a\pm c)$, y, asimismo, $\beta_\pm$ todos serán enteros. Por desgracia, si $a$ $b$ son ambos impares, entonces no hay manera de elegir a $c$ $d$ tanto extraña, pues, a continuación, $ac+bd$ siempre será incluso — este es el "tablero de ajedrez" obstrucción, que cada secuencia de movimientos conducirá a un cuadrado del mismo color (es decir, con $x+y$ tener la misma paridad) como el punto de partida de la plaza.
Por otro lado, esta construcción muestra que el tablero de ajedrez obstrucción es esencialmente la única obstrucción; a partir de $a, b$ de enfrente de la paridad (de nuevo, se puede elegir arbitrariamente $a$ como el impar) con $\gcd(a,b)=1$, entonces podemos encontrar $c, d$ tal que $ac+bd=1$ mediante el algoritmo de Euclides, a continuación, encontrar $\alpha_\pm$ $\beta_\pm$ a partir de las ecuaciones anteriores; estos valores dan el movimiento de la secuencia necesaria para llegar a $(1, 0)$, y a partir de ahí podemos llegar a cualquier otro lugar en la (presunta infinito) de la junta. (Un ejercicio interesante es probar y encontrar el más pequeño de la junta en la que se puede llegar a todas partes, teniendo en cuenta los efectos de borde — la $(n, n-1)$ caso hace un lindo desafío).
Para agregar una expresión algebraica enfoque va en la misma dirección como Steven Stadnicki excelente respuesta:
Vamos a llamar a cualquier combinación de movimientos de una traducción. Si la junta era infinito, el conjunto de todas las posibles traducciones de el caballero iba a formar un subgrupo del grupo aditivo $\Bbb Z \times \Bbb Z$. Por lo tanto, la pregunta podría ser reformulado como si $ (\pm a,b)$,$(\pm b,a)$ generar $\Bbb Z \times \Bbb Z$.
Esto es obviamente falso si $(a,b)$ no coprime. Así que supongamos $a,b$ son coprime y deje $$G:=\langle (\pm a,b),(\pm b,a)\rangle \subseteq \Bbb Z \times \Bbb Z$$ Está claro que $(0,2a),(0,2b) \in G$, por lo tanto $(0,2) \in G$. Del mismo modo, $(2,0) \in G$, mostrando el $2\Bbb Z \times 2\Bbb Z \subseteq G$. Así que la única pregunta que queda es si las imágenes de $(a,b),(b,a)$ generar $\Bbb Z/2\Bbb Z \times \Bbb Z/2\Bbb Z$. Este es el caso de la fib $(a,b) \not \equiv (b,a)$$\Bbb Z/2\Bbb Z \times \Bbb Z/2\Bbb Z$, o, equivalentemente,$(a,b) \not \equiv (1,1) \bmod 2$.
En otras palabras:
En un infinito de la junta de el caballero llega a todas las posiciones iff $a,b$ coprime y de distinta paridad.
Tenga en cuenta que este argumento puede ser traducido a $\Bbb N \times \Bbb N$ si la junta directiva debe estar acotada a la izquierda y a la parte inferior de $(0,0)$.
El caballero sólo puede moverse en posiciones como$$(x,y) = (a(m_a-n_a)+b(m_b-n_b),a(r_a-s_a)+b(r_b-s_b))$$ donde
De hecho, a considerar sólo el movimiento en $x$-eje: vamos a $m$ el número de veces que el caballero va a la derecha, y $n$ el número de veces que el caballero va a la izquierda. A continuación, se obtiene que, después de algunos movimientos, el caballero está en la $(am_a + bm_b-an_a -bn_b) = (a(m_a-n_a)+b(m_b-n_b))$-ésimo de la ranura, donde$m_a+m_b = m$$n_a +n_b =n$. Ahora, vamos a echar un vistazo en el movimiento vertical: en cada movimiento (derecha o izquierda) el caballero también puede ir hacia arriba o hacia abajo. Deje $r$ el número de veces que el caballero va hacia arriba y $s$ el número de veces que el caballero va hacia abajo. Del mismo modo que el caballero puede llegar a todas las ranuras en la forma $(ar_a + br_b-as_a -bs_b) = (a(r_a-s_a)+b(r_b-s_b))$-ésimo de la ranura, donde$r_a+r_b = r$$s_a +s_b =s$. Claramente $r+s=m+n$.
Así que las posiciones que el caballero puede llegar en forma $(a(m_a-n_a)+b(m_b-n_b),a(r_a-s_a)+b(r_b-s_b))$
Tenga en cuenta que si $GCD(a,b) = g > 1$ entonces el caballero sólo puede llegar a posiciones múltiples de $g$.
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.
