NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 26/03/2012 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	Jeux et problèmes
Débutants Général	ÉCHECS			Glossaire Général
INDEX Jeux	Introduction & invention	Solutions	Cavalier	Dame / Reine
		Pavage		Fou
		Sommaire de cette page >>> Échiquier et dominos >>> Problème de l'échiquier tronqué >>> Problème de l'échiquier à trous >>> Pas de dominos >>> Polyominos

ÉCHECS & DOMINOS

Pavage de l'échiquier abîmé par des dominos

Recouvrir l'échiquier complet avec des dominos est facile (trivial). On place noir sur noir et blanc sur blanc.

Il existe une variété de problèmes de recouvrement de l'échiquier dont on a supprimé certaines cases.

En particulier, retrait de deux cases blanches (64 – 2 = 62 carrés) et le recouvrir avec 31 dominos (31 x 2 = 62 carrés).

ÉCHIQUIER & DOMINOS
Échiquier tronqué	Échiquier à trous
On retire deux cases de mêmes couleurs.	On retire deux cases de couleurs différentes.
IMPOSSIBLE >>>	TOUJOURS POSSIBLE >>>
Ce résultat est connu sous le nom de théorème de Gomory Problème posé par Gamov et Stern en 1958 et publié par Martin Gardner dans la revue Scientific American. Anglais: The mutilated chessboard problem Il est possible de généraliser ce type de problème au pavage d'un plateau de n x n abîmé de m cases par un k-omino.

Voir Jeux de taquin

PROBLÈME DE L'ÉCHIQUIER TRONQUÉ

Problème

Peut-on couvrir un échiquier tronqué de deux cases de même couleur de avec des dominos ?

Réponse

Non ! Il y deux approches possibles :

l'expérimentation en examinant tous les cas et en constatant que c'est impossible: démarche du scientifique.

la démonstration logique aboutissant à une conclusion indéniable.

Illustration

Les deux cases blanches des côtés sont retirées 

Démonstration

1	L'échiquier tronqué possède	32 cases noires et 30 blanches.
2	Un domino couvre toujours	1 case noire et 1 blanche.
3	30 dominos couvrent	30 cases noires et 30 blanches.
4	Il reste 1 domino pour	2 cases noires.
5	Or un domino ne peut pas couvrir	2 cases de la même couleur.

En bref: en posant les dominos, j'aurai toujours autant de cases blanches que de noires couvertes. Or sur l'échiquier tronqué, j'ai moins de cases blanches. D'où impossibilité pour obtenir le recouvrement.

De nombreuses démonstrations procèdent ainsi: on cherche des impossibilités par raisonnement général. Ici, en impliquant une sorte de parité.

Voir Dualité

PROBLÈME DE L'ÉCHIQUIER À TROUS

Problème On retire deux cases de couleurs différentes à un échiquier. Peut-on le recouvrir avec 31 dominos ? Réponse Oui ! Une condition nécessaire est déjà remplie: il y a autant de cases de chaque couleur sur l'échiquier. Son recouvrement par domino est possible. Mais est-ce suffisant? Voici une manière illustrée d'appréhender la solution. On retire, par exemple, les deux cases marquées en jaune. On recouvre avec les dominos en suivant une espèce de labyrinthe, tracé ici en rouge. Entre les deux cases jaunes, il y a toujours un nombre pair de cases. On part d'une blanche d'un côté pour aboutir à une noire de l'autre Grâce à cet artifice, on montre bien que la solution existe toujours

Aucun DOMINO

Problème

Combien de cases faut-il retirer pour empêcher de poser un seul domino sur l'échiquier?

Réponse

32 cases de la même couleur.

Problème

Même question, mais avec une croix grecque (pentomino

).
On doit éliminer le minimum de cases pour rendre impossible la pose d'une croix grecque

Réponses

Solution évidente 16 cases à éliminer

Solution optimum 10 cases à éliminer

---

Suite	Cavalier Pavage avec dominos Voir haut de page
Voir	Intelligence artificielle Jeux et énigmes – Index Morpion solitaire Pentominos Polyominos
Cette page	http://villemin.gerard.free.fr/Puzzle/EchecPav.htm