Sachant que deux rois situés sur deux cases qui se touchent par un côté ou par un coin s'attaquent, combien peut-on disposer de rois au maximum sur un échiquier (de taille 8 fois 8) sans qu'aucun n'attaque un autre.

Accordéon
Titre
Solution
Texte

Si l'on essaie de placer un à un des rois sur un échiquier, il est nature de les placer les plus près possibles l'un de l'autre. Ainsi, on commencera par la case A1, et on mettra ensuit des rois en A3, C1 et C3. Puis, on pourra en placer aux cases A5, C5, E5, E3 et E1. Et enfin, aux cases A7, C7, E7, G7, G5, G3, et G1.

roissol.jpg

Au total, on aura ainsi placé 16 rois, et il n'est pas possible d'en placer un 17ème sans qu'il n'attaque un des précédents. Mais pourquoi cette configuration serait-elle optimale ? Si d'autre part l'on doit tester toutes les configurations possibles, cela risque de prendre un peu trop de temps...

En fait, il s'agit d'une application ingénieuse du principe des tiroirs : on peut découper l'échiquier en 16 parties, chacune constitué de 4 cases disposées en carré des cases qui s'attaquent, donc. (cf la figure qui suit, où les découpages sont représentés en pointillés rouges)

roisdecoupe.jpg

Supposons donc que l'on ait disposé 17 rois sur l'échiquier. D'après le principe des tiroirs, au moins 2 d'entre- eux se trouvent dans la même case, donc s'attaquent mutuellement !

On peut placer au maximum 16 rois sur un échiquier.