Énigme de la semaine 30

Au pénitencier.

(Extrait du forum des énigmes mathématiques du site « l’île des mathématiques »)

Au pénitencier de Math Island, spécialisé dans la détention de dangereux criminels, le directeur est confronté à de nombreux problèmes de sécurité lors de l’appel quotidien.
Chaque matin, les détenus et les gardiens se placent sur un grand quadrillage de 8 cases sur 8 (chacun sur une case et toutes les cases sont occupées).
Si un prisonnier n’a pas de gardien à côté de lui pour le surveiller, il peut agresser une des personnes placées à côté de lui. De même, si un gardien n’a pas un autre gardien à côté de lui pour le protéger, il peut se faire agresser par un prisonnier.

 
 
 
Être placé à côté de quelqu’un signifie se trouver sur une des cases adjacentes à la sienne, c’est-à-dire ayant un côté en commun. Chaque prisonnier et chaque gardien doit donc avoir au moins un gardien à côté de lui (en diagonale, ça ne compte pas).
Il faut donc placer judicieusement un certain nombre de gardiens sur le quadrillage mais, par souci de rentabilité, on veut un maximum de prisonniers dans le pénitencier. Toutefois, le nombre total de détenus et de gardiens est forcément égal à 64.
 
 
 
 
Combien faut-il de gardiens au minimum pour assurer la sécurité au cours de l’appel et où doivent-ils être placés ?

Solution

Pour un carré , on peut montrer que le nombre minimal de gardiens est égal à .
Il faut au moins 20 gardiens pour assurer la sécurité.
Il existe de nombreuses manière de disposer ces 20 gardiens. En voici une :