Problème de l'échiquier mutilé
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.
Notes et références
- (en) Peter B. Andrews et Matthew Bishop, Theorem Proving With Analytic Tableaux and Related Methods : 5th International Workshop, Tableaux '96, Terrasini, Palermo, Italy, 15-17th, 1996, Proceedings, Springer-Verlag, coll. « Lecture Notes in Computer Science », (lire en ligne), « On Sets, Types, Fixed Points, and Checkerboards »
« most treatments of the problem in the literature solve it in the conceptual sense, but do not actually provide proofs of the theorem in either of McCarthy's original formulations. »
- (en) R. D. Arthan, The Mutilated Chessboard Theorem in Z, , PDF (lire en ligne)
« The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a “tough nut to crack” for automated reasoning. »
- (en) Michael Alekhnovich, « Mutilated chessboard problem is exponentially hard for resolution », Theoretical Computer Science, vol. 310, nos 1-3, , p. 513–525 (DOI 10.1016/S0304-3975(03)00395-5)
- (en) John McCarthy, AISB Workshop on Artificial Intelligence and Creativity, (lire en ligne), « Creative Solutions to Problems »
- (en) John J. Watkins, Across the board : the mathematics of chessboard problems, Princeton University Press, , 12–14 p. (ISBN 978-0-691-11503-0, lire en ligne)
- Selon Mendelsohn, la première publication est dans le livre de Honsberger. (en) N. S. Mendelsohn, « Tiling with dominoes », The College Mathematics Journal, Mathematical Association of America, vol. 35, no 2, (DOI 10.2307/4146865, JSTOR 4146865)
Voir aussi
Liens externes
- Dominoes on a Checker Board
- Gomory's Theorem by Jay Warendorff, The Wolfram Demonstrations Project.