Problème de l'échiquier mutilé
From Wikipedia, the free encyclopedia
Le problème de l'échiquier mutilé est un puzzle de pavage proposé par le philosophe Max Black dans son livre Critical Thinking (1946). Il a été débattu par Solomon W. Golomb (1954), par Gamow et Stern 1958 et par Martin Gardner dans sa rubrique "Jeux Mathématiques" dans Scientific American. Le problème est comme suit :
Supposons qu'un échiquier standard 8 × 8 ait deux coins diagonalement opposés enlevés, laissant 62 carrés. Est-il possible de placer 31 dominos de taille 2 × 1 afin de couvrir l'ensemble de ces carrés?
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
La plupart des considérations de ce problème dans la littérature apportent des solutions "au sens conceptuel" sans preuves[1]. John McCarthy, l'a présenté comme un problème difficile pour les systèmes de preuve automatisés[2]. En fait, sa solution utilisant le système de résolution d'inférence est exponentiellement difficile[3].
Solution
Le puzzle est impossible à réaliser. Un domino placé sur l'échiquier couvrira toujours un carré blanc et un carré noir. Par conséquent, une collection de dominos placée sur le plateau couvrira un nombre égal de carrés de chaque couleur. Si les deux coins blancs sont retirés du tableau, il reste 30 carrés blancs et 32 carrés noirs qui doivent être recouverts par des dominos, ce qui est impossible. Si les deux coins noirs sont supprimés, il reste alors 32 carrés blancs et 30 carrés noirs. Il est donc à nouveau impossible[4].
Théorème de Gomory
La même preuve d’impossibilité montre qu’il n’y a pas de pavage de dominos lorsque deux carrés blancs sont retirés de l’échiquier. Cependant, si deux carrés de couleurs opposées sont supprimés, il est toujours possible de paver le reste du tableau avec des dominos ; ce résultat s'appelle le théorème de Gomory[5] et est nommé d'après le mathématicien Ralph E. Gomory, dont la preuve a été publiée en 1973[6]. Le théorème de Gomory peut être prouvé à l'aide d'un cycle hamiltonien de la grille graphique formée par les carrés de l'échiquier ; la suppression de deux carrés de couleurs opposées divise ce cycle en deux chemins avec un nombre pair de carrés chacun, qui sont faciles à diviser en dominos.
