Principio del casillero para n reinas

Supongamos que tenemos un tablero 100 × 100 y lugar 100 reinas tales que ninguna ataque a otra. Demostrar que cada uno de los cuatro 50 × 50 sub-tableros (obtenidos al dividir el tablero en 4 ) contiene al menos una reina. Además, demuestre que si uno de los tableros contiene exactamente una reina, reemplazar reinas por caballos provocaría que los caballos se atacaran entre sí.

Mi enfoque ha sido usar que cada fila y columna debe contener solo una reina, luego utilizar el principio del casillero de alguna manera. Aún así, no estoy seguro de cómo es posible colocar solo una reina en 50 × 50 junta.

La pregunta es pedirle que muestre "cada subtablero tiene al menos una reina", no "al menos un subtablero solo tiene una reina".

Respuestas (1)

Cada fila debe contener exactamente una reina; cada columna debe contener exactamente una reina.

Supongamos que, en aras de la contradicción, el subtablero superior izquierdo no contiene reinas.

  • Esto implica que las 50 reinas en la mitad superior del tablero deben estar en el subtablero superior derecho.
  • Esto también implica que las 50 reinas en la mitad izquierda del tablero deben estar en el subtablero inferior izquierdo.

Dado que estos dos conjuntos de reinas son disjuntos, esto explica todas las 100 reinas: todas están en los subtableros superior derecho o inferior izquierdo.

Sin embargo, estos dos subtableros contienen sólo 2 ⋅ 50 − 1 = 99 diagonales, por lo que debe haber dos reinas en la misma diagonal en alguna parte. Esto es una contradicción.

Principio del casillero para n reinas
RespuestasAquíPolítica de privacidad1y, 0v