Subconjunto del movimiento del caballo en el ajedrez.

Question

Se permite que una partícula se mueva en el $\mathbb{Z}\times \mathbb{Z}$ rejilla eligiendo cualquiera de los dos saltos:

1) Mover dos unidades a la derecha y una unidad hacia arriba

2) Mover dos unidades hacia arriba y una hacia la derecha.

Dejemos que $P=(30,63)$ y $Q=(100,100)$ ¿Si la partícula comienza en el origen entonces?

a) $P$ es alcanzable pero no $Q$ .

b) $Q$ es alcanzable pero no $P$ .

c) Ambos $P$ y $Q$ son accesibles.

d) Ninguno de los dos $P$ ni $Q$ es alcanzable.

He podido comprobar que los movimientos dados son un subconjunto del de un caballo en el ajedrez. Creo que nunca sería capaz de alcanzar $(100,100)$ pero no estoy seguro de la razón. Tiene que ver con el movimiento del caballo, pero no sé qué.

No tengo mucha idea de ajedrez, así que me gustaría que alguien me contestara con más detalle.

Answer 1

Ambos movimientos posibles aumentan la suma de coordenadas en $3$ por lo que cualquier posición alcanzable debe tener la suma de coordenadas un múltiplo de $3$ . Esto significa que $Q$ no es alcanzable, ya que su suma de coordenadas es $200$ , no divisible por $3$ .

$P$ tampoco es alcanzable - para llegar a un $x$ -coordinación de $30$ debe hacer como máximo $30$ salta, lo que significa que el mayor $y$ -La coordenada que podría alcanzar es $2×30=60<63$ .

Answer 2

Los posts anteriores son sin duda respuestas suficientes, pero para divertirme he pensado en caracterizar con precisión el conjunto de puntos que se pueden alcanzar desde el origen.

Obsérvese que realizar un movimiento del tipo (1) equivale a añadir $(2,1)$ al vector de posición de la partícula, y, asimismo, un movimiento del tipo (2) equivale a añadir $(1,2)$ al vector de posición de la partícula. Por tanto, los puntos que la partícula puede alcanzar desde el origen son precisamente aquellos puntos de la forma $$ n(1,2) + m(2,1) = (n + 2m, 2n + m) $$ para enteros no negativos $n,m$ . Esta es una caracterización precisa de los puntos accesibles, pero no es muy fácil de comprobar.

Resulta que el conjunto de condiciones mucho más fácil de comprobar

1. $a + b$ es divisible por $3$

2. $2a \geq b \geq \frac{a}{2}$

son necesarios y suficientes para un punto $(a,b)$ para ser accesible.

Para ver esto, supongamos $(a,b)$ es accesible. Entonces existen enteros no negativos $n,m$ tal que \begin {align} n + 2m &= a \\ 2n + m &= b \end {align} Así, $$ a + b = 3n + 3m = 3(n + m) $$ que, desde $n,m$ son enteros no negativos, muestra que $a + b$ es divisible por $3$ . Resolver para $n$ y $m$ encontramos \begin {align} n &= \frac {1}{3}(2b - a) \\ m &= \frac {1}{3}(2a - b) \end {align} Desde $n,m$ son no negativo enteros, tenemos \begin {align} 0 & \leq \frac {1}{3}(2b - a) \\ 0 & \leq \frac {1}{3}(2a - b) \end {align} La primera de estas desigualdades implica $b \geq \frac{a}{2}$ y la segunda implica $b \leq 2a$ es decir $2a \geq b \geq \frac{a}{2}$ .

A la inversa, supongamos que las condiciones 1 y 2 se cumplen para algún punto $(a,b)$ . Por la condición 1, existe un número entero $k$ tal que $a + b = 3k$ . Toma $n = b - k$ y $m = a - k$ . Tenga en cuenta que $k = \frac{a + b}{3}$ . Calculamos \begin {align} n &= b - k = b - \frac {a + b}{3} = \frac {2b - a}{3} \geq \frac {2 \frac {a}{2} - a}{3} = \frac {a - a}{3} = 0 \\ m &= a - k = a - \frac {a + b}{3} = \frac {2a - b}{3} \geq \frac {2a - 2a}{3} = 0 \end {align} Así, $n$ y $m$ son enteros no negativos. Además \begin {align} (n + 2m, 2n + m) &= ((b - k) + 2(a - k) , 2(b - k) + (a - k)) = (b + 2a - 3k, 2b + a - 3k) \\ &= (b + a + a - 3k, b + b + a - 3k) = (3k + a - 3k, b + 3k - 3k) = (a,b) \end {align} Por nuestra caracterización original de los puntos accesibles, esto muestra que $(a,b)$ es un punto accesible.

Answer 3

Tenga en cuenta que a partir de $(x,y)$ podemos alcanzar $(X,Y)\in\{(x+2,y+1),(x+1,y+2)\}$ . En cualquier caso, si $X+Y-(x+y)$ es divisible por $3$ . Esto significa que si partimos del origen $(0,0)$ entonces no podemos alcanzar $(X,Y)$ si $X+Y$ no es divisible por $3$ . Así que tienes razón $(100,100)$ no es alcanzable.

¿Qué pasa con $(30,63)$ ?

Answer 4

Si $U$ es el número de movimientos de subida dos veces, y $R$ es el número de movimientos a la derecha dos veces, tenemos que la posición final es $(2R+U,R+2U)$

Para $P$ tenemos:

$ 2R+U = 30, R+2U=63$
$U = 30-2R$
$R+2(30-2R)=63$
$-3R+60=63$
$-3R=3$
$R=-1$

Como cada movimiento debe realizarse un número entero no negativo de veces, esto es imposible.

Para $Q$ , una matemática similar obtiene que $3R=100$ que tampoco permite una solución entera no negativa.

Answer 5

Sea a el recuento de la primera jugada y b el recuento de la segunda.

$$(x,y) = (2,1)a + (1,2)b$$

Donde x e y son enteros no negativos que representan nuestra posición y una posición es alcanzable si a y b son enteros no negativos.

$$x = 2a + b$$

$$y = 2b + a$$

Tenemos dos ecuaciones lineales y dos incógnitas, por lo que esperamos exactamente un par de a y b para cada par de x e y, la pregunta entonces es ¿son a y b enteros no negativos?

$$2y = 4b + 2a$$

$$2y - x = 3b$$

$$b=\frac{2y-x}{3}=y-\frac{x+y}{3}$$

$$x = 2a + \frac{2y-x}{3}$$

$$3x = 6a + 2y-x$$

$$4x -2y = 6a$$

$$a = \frac{2x-y}{3}=x-\frac{x+y}{3}$$

Exigir que a y b sean enteros no negativos nos da ahora varias condiciones.

1. $2y \geqslant x$
2. $x \geqslant 2y$
3. $x+y$ es divisible por 3

Su primera posición falla el criterio 1, su segunda posición falla el criterio 2.