¿Es posible colocar una reina y al menos 29 caballos en un tablero de ajedrez de 8x8 de modo que no haya 2 piezas que se ataquen entre sí?

¿Es posible colocar una reina y al menos 29 caballos en un 8? × 8 tableros de ajedrez tal que no hay 2 piezas que se ataquen?

Pensé en tratar de usar el límite ⌈ metro norte 2 ⌉ por el número de caballos en un metro × norte tablero de ajedrez de manera que no se ataquen entre sí, pero eso requiere metro , norte > 2 , y para algunas posiciones de reina, eso no se aplica.

También pensé que si tuviéramos una reina, hay como máximo 7 filas para colocar los caballos, entonces tiene que haber 5 caballos en una fila. Aunque no estoy seguro de qué uso podría tener eso.

¿Eh? Su respuesta puede ser correcta, pero no creo que su razonamiento lo sea. ¿Por qué varios caballeros no pueden atacar el mismo cuadro vacío?
Puedes poner 32 caballeros en un 8 × 8 tablero de ajedrez, sin que ninguno de ellos ataque a otro, simplemente colocando un caballo en cada casilla blanca (o negra).
@justadumbguy: ¿Estás seguro de que no hay un error tipográfico en tu problema? Creo 29 es demasiado grande para trabajar. ¿Podría la pregunta indicar en su lugar 19 ? Eso funciona.
@ DavidG.Stork, ¿cómo se transforma este problema en uno combinatorio, resuelto con técnica algebraica o combinatoria? Estos acertijos desafían la parametrización por lo que puedo decir
@FShrike: De hecho. Creo que el único enfoque viable es la búsqueda por computadora... posiblemente con algún aumento en la eficiencia basado en las simetrías del problema (por ejemplo, solo necesitamos considerar posiciones para la reina en un cuadrante). De todos modos, mi respuesta actual al OP es: "no".
@DavidG.Stork ¿Cómo colocas 24 caballos en el tablero sin que uno de ellos ataque a la dama? no puedo hacerlo mejor que 22 .
@RobertShore: Perdóname... Me equivoqué. Noté que dos de mis caballos atacaron a la reina, así que sí: 22. (Eliminaré el comentario anterior). Gracias. Sin embargo, creo que estamos de acuerdo en que la respuesta a la pregunta del OP es "no".
¿Importan los lados (por ejemplo, 14 caballos blancos y 15 negros)?
Si los lados importan, aquí hay una solución: chessvideos.tv/bimg/126omnfkdyz6.png Pero si los lados no importan, entonces no es una solución...

Respuestas (2)

En primer lugar, aquí está la prueba de que no puede poner más de 32 caballeros no atacantes en un tablero de ajedrez. Puedes emparejar los cuadrados del tablero en 32 pares, donde cada par está separado por un movimiento de caballo, como se muestra a continuación. Como puede colocar como máximo un caballo en cada pareja, puede colocar como máximo 32 caballeros

Ahora, imagina colocar una reina en alguna casilla en este mismo diagrama, y ​​luego colocar una X en cada casilla atacada por la reina, así como una X en las casillas a las que un caballo se aleja de la reina. No importa dónde coloques a la reina, al menos 4 de estos pares tendrán ambos cuadrados marcados con X. Por lo tanto, el número de caballos que puedes colocar se reduce en al menos cuatro, por lo que no puedes colocar más de 28 caballeros

Por ejemplo, cuando la reina se coloca en A 1 , la esquina inferior izquierda, luego los pares A 1 − C 2 , A 2 − C 1 , B 2 − D 1 , y A 4 − C 3 están todas marcadas con una X (la letra es la columna y el número es la fila). No es demasiado difícil verificar caso por caso que la dama siempre sale X al menos 4 de estos pares. De hecho, a medida que la dama se acerca al centro, saca más parejas.

A través de la programación lineal entera, descubrí que si fuerza al menos una reina, puede colocar como máximo 22 caballeros, y aquí hay una de esas soluciones:

. norte . norte . norte . . norte . norte . norte . norte . . norte . norte . norte . . norte . norte . norte . norte . . norte . norte . norte . . norte . norte . norte . . . . norte . norte . . . . . . . . . . . q

Como en este problema donde la dama es reemplazada por una torre , para cada uno de los 10 Colocaciones esencialmente diferentes de la reina, la dualidad de programación lineal proporciona un certificado de optimización. Por ejemplo, si la reina se coloca en la esquina inferior derecha, la siguiente partición de los cuadrados restantes no atacados en 22 conjuntos muestra que a lo sumo 22 Los caballeros se pueden colocar:

. 19 1 20 2 3 4 . 1 . 2 5 4 6 21 . 7 8 . 9 10 5 3 . 11 12 7 . 13 9 6 . 8 14 15 12 . 10 dieciséis . 17 11 18 13 dieciséis . . . 14 15 17 22 18 . . . . . . . . . . .
Este es un refinamiento del enfoque mostrado por @Mike Earnest, y produce certificados similares para los otros 9 casos.

¿Es posible colocar una reina y al menos 29 caballos en un tablero de ajedrez de 8x8 de modo que no haya 2 piezas que se ataquen entre sí?
RespuestasAquíPolítica de privacidad1y, 0v