Problème des rois sur un échiquier : solution.

Si l'on essaie de placer un à un des rois sur un échiquier, il est nature de les placer les plus prè 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, chacunes 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'entres eux se trouvent dans la même case, donc s'attaquent mutuellement !

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