Problème de l'échiquier mutilé

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
abcdefgh
8
Chessboard480.svg
Case noire h8 vide
Case noire a1 vide
8
77
66
55
44
33
22
11
abcdefgh
Mutilated chessboard problem

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ébattue par Solomon W. Golomb (1954), par Modèle:Harvtxt 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?

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[modifier | modifier le code]

A mutilated chessboard problem example.
Exemple d'un échiquier mutilé montrant des carrés vides de même couleur (notez les deux carrés noirs vides au milieu) 

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[modifier | modifier le code]

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.

Références[modifier | modifier le code]

  1. (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)
  2. (en) R. D. Arthan, The Mutilated Chessboard Theorem in Z, , PDF (lire en ligne)
  3. (en) Michael Alekhnovich, Mutilated chessboard problem is exponentially hard for resolution, vol. 310, , 513–525 p. (DOI 10.1016/S0304-3975(03)00395-5)
  4. (en) John McCarthy, AISB Workshop on Artificial Intelligence and Creativity, (lire en ligne)
  5. (en) John J. Watkins, Across the board: the mathematics of chessboard problems, Princeton University Press, , 12–14 p. (ISBN 978-0-691-11503-0)
  6. Selon Mendelsohn, la première publication est dans le livre de Honsberger. (en) N. S. Mendelsohn, Tiling with dominoes, vol. 35, Mathematical Association of America, , 115–120 p. (DOI 10.2307/4146865, JSTOR 4146865)

Liens externes[modifier | modifier le code]