¿Quién tiene una estrategia ganadora en "knight" y por qué?

Question

Tal vez, este juego ya es conocido, pero no encontré nada al respecto, lo llamo lo llamo "caballero".

Las reglas :

El jugador 1 elige la casilla inicial de un caballo en un tablero normal de 8x8. Los jugadores mueven alternativamente el caballo a una casilla que no haya sido que no haya sido visitada. El jugador que no tenga más movimientos pierde.

¿Qué jugador tiene una estrategia ganadora y por qué?

Answer 1

El $m\times n$ gráfico del caballero es el gráfico cuyos vértices son los cuadrados del $m\times n$ tablero de ajedrez, dos casillas son adyacentes si un caballo puede pasar de una a otra.

El jugador 2 tiene una estrategia ganadora obvia en el $m\times n$ tablero de ajedrez si el gráfico del caballo correspondiente tiene un la combinación perfecta es decir, mueve el caballo a la casilla que coincide con la casilla actual del caballo. En particular, suponiendo que $mn$ es par, el jugador 2 tiene una estrategia ganadora si el gráfico del caballo tiene un Trayectoria hamiltoniana En términos ajedrecísticos, si un tour del caballero (abierto o cerrado) existe.

Por lo tanto, el jugador 2 tiene una estrategia ganadora en la normal $8\times8$ tablero de ajedrez y muchos otros. En concreto, el jugador 2 tiene una estrategia ganadora en tableros de los siguientes tamaños:
(a) $m\times n$ donde $m,n\ge5$ y $mn$ está en paz;
(b) $2\times n$ donde $n$ es divisible por $4$ ;
(c) $3\times n$ donde $n$ es par y $n\ge4$ ;
(d) $4\times n$ donde $n\ge2$ .

Para el caso (a) podemos utilizar el hecho que existe una gira de caballeros. Para los demás casos, basta con observar que el $2\times4$ , $3\times4$ y $3\times6$ Los gráficos del caballero tienen emparejamientos perfectos, ya que los tableros de los casos (b), (c) y (d) se pueden embaldosar con $2\times4$ , $3\times4$ y $3\times6$ tablas.

De forma similar, se puede demostrar que el jugador 1 gana en todos los demás casos. Es decir, el jugador 1 tiene una estrategia ganadora en tableros de los siguientes tamaños:
(e) $m\times n$ donde $mn$ es impar;
(f) $1\times n$ donde $n\ge1$ ;
(g) $2\times n$ donde $n$ no es divisible por $4$ .

Ejemplo. Aquí hay una "coincidencia perfecta" para lo ordinario $8\times8$ tablero de ajedrez:

a1c2, b1d2, c1a2, d1b2, e1g2, f1h2, g1e2, h1f2,
a3c4, b3d4, c3a4, d3b4, e3g4, f3h4, g3e4, h3f4,
a5c6, b5d6, c5a6, d5b6, e5g6, f5h6, g5e6, h5f6,
a7c8, b7d8, c7a8, d7b8, e7g8, f7h8, g7e8, h7f8.

Es decir, la casilla a1 se empareja con la casilla c2, la b1 se empareja con la d2, y así sucesivamente. Tenga en cuenta que las 64 casillas están divididas en pares no superpuestos, y cada conjunto de casillas emparejadas está separado por un movimiento de caballo. La estrategia ganadora para el jugador 2 es DONDEQUIERA QUE EL JUGADOR 1 PONGA EL CABALLO, MOVERLO A LA OTRA CASILLA DEL MISMO PAR. Por ejemplo, si el jugador 1 comienza la partida dejando caer el caballo en e8, el jugador 2 responde jugando Cg7. Si el jugador 1 juega ahora Ne6, el jugador 2 juega Ng5, y así sucesivamente. Aquí hay un ejemplo de partida, con el jugador 1 haciendo jugadas al azar, y el jugador 2 siguiendo la estrategia ganadora descrita anteriormente:

1. 1. Ne8 Ng7 2. Ne6 Ng5 3. Cf3 Nh4 4. Cf7 Nh8 Cf5 Ch6 5. Cf7 Ch8 6. Cg6 Ne5 7. Cc6 Na5 8. Cb3 Cd4 9. Ne2 Cg1 10. Ch3 Cf4 11. Nh5 Cf6 12. Ng4 Ne3 13. Nc5 Na3 14. Cb1 Cd2 15. Cf1 Ch2 y el jugador 2 gana.

P.D. Por supuesto, la estrategia sigue funcionando si se permite a las blancas mover el caballo a cualquier casilla no visitada ya, y sólo las negras están limitadas a hacer movimientos de caballo.