Problema de independencia: una torre y número máximo de caballos en el tablero de ajedrez 8×88×88 \times 8

$25$es el máximo posible y puede ser probado por distinción de casos.

Primero, observe que por un argumento de simetría, podemos reducir el número de ubicaciones para la torre a$10$. Aquí están las posibles ubicaciones para la torre:

Ahora bien, hay pocas observaciones que hacer y pocos hechos que mencionar:

• Dejar$K(n)$ser el número máximo de caballos no atacantes que se pueden colocar para$n\times n$junta. Entonces ( fuente ),

  $$K(n) = \begin{cases} \frac{n^2}{2}, & \text{if $n$ is even} \\[2ex] \frac{n^2+1}{2}, & \text{if $n$ is odd} \end{cases}$$

• Cuando dividimos un tablero en$m$tableros rectangulares con$K_i$siendo el número máximo de caballeros no atacantes que se pueden colocar para$i^{th}$tablero pequeño, tenemos

  $$K \le \sum_{i = 1}^m K_m$$ dónde$K$es el número máximo de caballos no atacantes que se pueden colocar en un tablero no dividido.

• Podríamos tener diferentes límites superiores para diferentes divisiones de tableros. Pero al final, estamos tratando de encontrar el límite superior mínimo.

• cuando tenemos un$4\times n$tablero con$n \ge 2$, número máximo de caballeros no atacantes que se pueden colocar$K_4(n) = 2n$. Incluso para$n$'s, esto es realmente fácil de probar dividiendo el tablero en$2\times4$tableros pequeños entonces ya sabemos$K_4(2) = 4$(mi respuesta anterior). por impar$n$'s, primero debemos observar$K_4(3) = 6$(se puede ver por ensayo y error). Entonces para$K_4(5)$, solo estamos agregando un$2\times4$pieza de tablero para$3\times4$junta. Aquí, puede usar la inducción para obtener el resultado.

• cuando tenemos un$1 \times n$tablero, obviamente, el número máximo de caballos no atacantes que se pueden colocar es$n$. Pero intentaremos evitar divisiones donde tengamos este caso. En su lugar, intentaremos con el siguiente.

• Cuando tenemos un caso como el que se muestra a continuación en el que no podemos colocar caballos en la línea roja, podemos considerar el lado izquierdo y el lado derecho de la línea como uno solo.$2 \times k$pieza de tablero. Esto se debe a que cuando tenemos un$2\times k$tablero, siempre que coloquemos un caballo a la izquierda$1\times k$parte, amenaza$1$o$2$cuadrados a la derecha$1\times k$parte. Tenga en cuenta que esto es lo mismo para el caso a continuación.

  Y para encontrar el número máximo de caballos no atacantes que se pueden colocar, podemos dividir el tablero (las líneas verdes lo dividen) como en la figura y ver que para cada$4$cuadrados entre las líneas verdes, podemos colocar$2$caballeros

• Cuando nosotros tenemos$3 \times 5$tablero, podemos colocar como máximo$8$caballeros Esto también vale la pena mencionarlo porque veremos mucho este caso. Para demostrarlo podemos dividirlo en$3 \times 3$donde es maximo$5$, y$2 \times 3$donde es maximo$4$. Así que nuestro límite superior es$9$. Pero, sólo hay dos formas de colocar$5$caballeros a$3 \times 3$tablero (que se muestra a continuación). En ambos casos, puede ver que no podemos colocar más de$3$caballeros a$2 \times 3$junta. Por lo tanto,$9$no es alcanzable. Tenga en cuenta que esta será nuestra principal idea de prueba de aquí en adelante .
  

Ahora, podemos ver los casos. Escribiré el número máximo de caballos para cada división y las muescas rojas indicarán dónde los caballos pueden amenazar a la torre (por lo tanto, no podemos colocar caballos):

Caso 1: Torre en a1. Este es un caso fácil ya que nos deja con$7 \times 7$tablero donde no podemos colocar caballos a dos de casillas blancas. pero en eso$7 \times 7$tablero, hay$25$cuadrados negros Entonces tenemos$K_{a1} \le K(7) = \frac{7^2+1}{2} = 25$por el primer hecho y de hecho podemos colocar$25$caballeros como usted sugirió.

Caso 2: Torre en b1. Podemos dividir el tablero de la siguiente manera:

Aquí tenemos$26$como límite superior. Sin embargo, esto todavía no está mal porque para lograr$26$, todas las divisiones deben tener el máximo posible de caballos. Por lo tanto, cada vez que demostramos que no podemos lograr el máximo de una división, el límite superior se convierte en$25$.

Ahora, para la parte azul del tablero, la colocación de$8$caballeros es único (se muestra a continuación). Y cuando hacemos esa colocación,$3$cuadrados de$3 \times 5$el tablero está amenazado (se muestra con muescas negras). Y dividirlo en un$3 \times 3$y un$2 \times 3$tablero, si usamos todos$3$cuadrados no amenazados de$2 \times 3$, no podemos colocar$5$caballeros a$3 \times 3$junta. Por lo tanto, no podemos colocar$8$caballeros a parte azul y $3 \times 5$junta. Por lo tanto,$26$no es alcanzable en este caso.

Caso 3: Torre en b2. Podemos dividir el tablero de la siguiente manera:

Aquí tenemos$K_{b2} \le 25 = 13+6+4+2$.

Caso 4: Torre en c1. Podemos dividir el tablero de la siguiente manera:

Aquí, de nuevo tenemos$26$como límite superior. Pero si enfocamos el lado izquierdo del tablero, podemos ver que si colocamos$2$caballeros a$2 \times 2$tablero, no podemos colocar$6$caballeros a$2 \times 5$tablero (que se muestra a continuación). Por lo tanto,$26$no es alcanzable en este caso.

Caso 5: Torre en c2. Podemos dividir el tablero de la siguiente manera:

Aquí tenemos$26$como límite superior. Pero la parte verde tiene una ubicación única para$6$caballeros (que se muestra a continuación). Después de esa colocación, podemos observar que para$2 \times 5$tablero, colocación de$5$los caballeros están determinados. Después de eso, debemos notar que no podemos colocar$8$caballeros a$3 \times 5$junta. Por lo tanto,$26$no es alcanzable.

Caso 6: Torre en c3. Podemos dividir el tablero de la siguiente manera:

Entonces nosotros tenemos$K_{c3} \le 25 = 13+5+5+2$.

Caso 7: Torre en d1. Podemos dividir el tablero de la siguiente manera:

Entonces nosotros tenemos$K_{d1} \le 25 = 14+6+5$.

Caso 8: Torre en d2. Podemos dividir el tablero de la siguiente manera:

Aquí, de nuevo tenemos$26$como límite superior. Pero es fácil ver que si colocamos$4$caballos a la parte azul, no podemos colocar un máximo de$2$caballeros a$2 \times 1$junta. Por lo tanto,$26$no es alcanzable en este caso.

Caso 9: Torre en d3. Podemos dividir el tablero de la siguiente manera:

Entonces nosotros tenemos$K_{d3} \le 25 = 10+8+4+3$.

Caso 10: Torre en d4. Podemos dividir el tablero de la siguiente manera:

Entonces nosotros tenemos$K_{d4} \le 25 = 8+6+6+5$.

Por lo tanto, el número máximo posible es$25$.

Desafortunadamente, esta es una solución muy larga y en algunos de$10$casos, encontramos que el límite superior es$26$y obligado a probar$26$no fue posible (tal vez hay algunas divisiones de tablero donde$25$es el límite superior para estos casos malos ). No pude ver una manera de mostrar$25$es el máximo posible sin distinción de casos de colocación de torres. Si hay una manera más fácil, también me alegra ver eso.

De hecho, estoy publicando esto para darle una idea, ya que no creo que esta respuesta esté completa.

A continuación se muestra el tablero de ajedrez con la colocación de su torre. Ahora, dividamos el resto del tablero en$4$Tableros pequeños de la siguiente manera:

Ahora, podemos ver que para$3 \times 3$parte, la colocación máxima es con$5$caballeros, que podemos verificar incluso probando todos los casos (pero la colocación no es única). Para$3 \times 4$piezas, la colocación máxima es con$6$caballeros, pero esta colocación puede no colocar todos$6$caballos a casillas blancas o negras. Pero no nos importa por ahora. Para$4 \times 4$parte, la colocación máxima es con$8$caballeros Probaré esto aquí ya que la idea de la prueba nos será útil más adelante:

Supongamos por una contradicción que podemos colocar$9$caballeros a$4 \times 4$junta. Entonces, dividamos el tablero en dos como sigue:

Entonces, por el principio del casillero, uno de los$2 \times 4$los cuadrados deben tener$5$caballeros Pero nuevamente, incluso probando todos los casos, podemos ver que no podemos ubicar$5$caballeros en$2 \times 4$tablero con la condición dada, por lo tanto$8$es el número máximo de caballos para$4 \times 4$junta.

Ahora, podemos colocar el máximo de$5$caballeros a$3 \times 3$junta,$6$caballeros a$3 \times 4$tableros y$8$caballero a$4 \times 4$tablero, que da$5+2\cdot6+8 = 25$y suponiendo$26$nos dará un resultado similar a$4 \times 4$caso (Podemos suponer para una contradicción y probar$26$caballeros no es posible).

Ahora, esta no es una respuesta completa porque cuando colocamos la torre en otro lugar, digamos b2, nos quedamos con una$6 \times 6$tablero, dos$1 \times 6$tableros y un$1 \times 1$junta. Aquí por$1 \times 6$tablas, si las tomamos por separado, podemos colocar$6$caballeros a ellos, lo que nos impedirá utilizar el argumento anterior. Todavía estoy publicando esto ya que puede darte alguna idea a ti y a otros.

En cada uno de los 10 casos de colocación de torres considerados por @ArsenBerk, puede obtener un certificado de optimización a través de la dualidad de programación lineal. Después de eliminar las casillas atacadas por la torre, introduce una variable de decisión$x_{i,j}$, delimitado por 0 y 1, para cada cuadrado restante$(i,j)$. La interpretación es que$x_{i,j}=1$si y solo si es cuadrado$(i,j)$contiene un caballero. Ahora el problema de programación lineal es maximizar$\sum_{i,j} x_{i,j}$sujeto a restricciones de conflicto de la forma$x_{i,j} + x_{i',j'} \le 1$, donde los cuadrados$(i,j)$y$(i',j')$son un movimiento de caballo el uno del otro. En cada caso, el valor objetivo óptimo es 25, y las variables duales óptimas indican una partición del tablero en$s$cuadrados individuales y$p$pares de cuadrados en conflicto con$s+p=25$. Trivialmente, cada cuadrado puede contener como máximo un caballo, y cada par puede contener como máximo un caballo, por lo que esta partición demuestra que se pueden colocar como máximo 25 caballos. Esta idea es muy similar a las particiones de @ArsenBerk en subconjuntos de cuadrados más grandes, pero aquí la partición se deriva automáticamente como un subproducto de la resolución de LP, y el certificado no se basa en resultados óptimos para tableros más pequeños.

Por ejemplo, aquí hay una partición de este tipo en 25 regiones (21 pares y 4 singletons) cuando la torre se coloca en el cuadrado b1:

 1  . 22  2  3  4 23  5 
 6  .  1  4  7  5  3  8 
24  .  6  9  2  8 10 11 
12  . 13  7 14 11 15 16 
13  . 12 17  9 18 19 10 
 .  .  . 14 20 21 16 15 
25  . 20  . 17 19 18 21 
 .  R  .  .  .  .  .  .