Rompecabezas | Número máximo de reyes en el tablero de ajedrez sin bajo jaque

Requisito previo: el principio del casillero Enunciado del
problema: dado un tablero de ajedrez de 8 × 8, calcule el número máximo de reyes que se pueden colocar en el tablero de ajedrez para que no haya dos reyes que se ataquen entre sí, es decir, ninguno de los reyes está bajo jaque. Un rey puede moverse solo un paso a la vez en cualquier dirección en el tablero de ajedrez (horizontal, vertical y diagonal).

Explicación:
según el principio del casillero, si tenemos n+1 palomas y tenemos n casilleros (o más bien jaulas), entonces debemos tener un hoyo (o jaula) con más de una paloma.

Por ejemplo si tuviera 6 bolas y 5 cajas. Pongo todas las bolas en las cajas (cualquier caja puede tener cualquier cantidad de bolas). Entonces, el principio del casillero establece que no importa cómo coloques las bolas dentro de las cajas, siempre habrá al menos una caja que tenga más de una bola. Es un principio muy intuitivo en matemáticas y, sin embargo, los problemas asociados con el principio son muy difíciles de comprender.

Entonces, aquí está el tablero de ajedrez. ¿Este problema tiene algo que ver con el principio del casillero?

Figure – 8×8 Chessboard

La respuesta a este problema es 16. Pero, ¿cómo llegamos a esta solución? Lo que hay que tener en cuenta en este rompecabezas es que cada vez que tenemos dos reyes dentro de un cuadrado de 2 × 2, siempre están bajo jaque:

No importa cómo coloquemos 2 reyes dentro de un tablero de ajedrez de 2×2, siempre los tendremos bajo jaque. Por esta observación, podemos concluir fácilmente que podemos tener como máximo un rey dentro de un cuadrado de 2×2.

Podemos imaginar un cuadrado de 2×2 como un agujero (jaula) para nuestra paloma, es decir, reyes. Entonces, un cuadrado de 2×2 ocupa 4 unidades cuadradas de área. El área total del tablero de ajedrez cuadrado es de 64 unidades cuadradas (suponiendo que el tamaño del tablero de ajedrez sea de 8 unidades × 8 unidades). Entonces, tenemos 64/4 = 16 jaulas o huecos en este escenario.

Podemos colocar fácilmente un rey en cada uno de estos grandes cuadrados de 2×2. Después de completar 16 reyes, siempre tendríamos un escenario en el que dos reyes se colocan en un cuadrado de 2 × 2 (según el principio de Pigeon Hole). Esto viola nuestra condición inicial y, por lo tanto, podemos tener un máximo de 16 reyes que satisfagan la condición anterior.

Figure – Possible solution

Figure – Another possible solution

Fórmula generalizada:
incluso para un cuadrado de × n, el tamaño de la jaula (cuadrado de 2 × 2) sigue siendo el mismo y podemos decir fácilmente que siempre que exceda la cantidad de jaulas posibles, definitivamente tendrá dos reyes dentro de un cuadrado de 2 × 2. Por lo tanto, el número máximo de jaulas viene dado por:

Este artículo es una contribución de Ankit Jain . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.