NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 04/03/2021

Orientation générale        DicoMot Math          Atlas                   Actualités                       M'écrire

Barre de recherche          DicoCulture              Index alphabétique        Références      Brèves de Maths

             

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

>>> Sur une barre d'épaisseur 2

>>> É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 cependant 12 988 816 façons de le faire

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).

Anglais: Domino tiling or dimer coverings 

 

 

Sur une barre d'épaisseur 2

 

Sur une grille 2 x n  la quantité de configurations de dominos arrangés est le nombre de Fibonacci Fn + 1 .

 

Deux exemples: pour n = 3, F4 = 3 et pour n = 4, F5 = 5.

 

Sur une grille 2n x 2n, la quantité de configurations grimpe à grande vitesse. Pour n de 0 à 4, on a: 1, 2, 36, 6 728, 12 988 816.

Le dernier cas étant celui de l'échiquier classique (8 x 8).

La formule de calcul est compliquée (Voir Domino Tiling - MathWorld)

 

 

 

ÉCHIQUIER & DOMINOS - Approche

É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 or

Covering a chess board with 2 missing places with 31dominoes

 

*    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 / Pavage avec dominos (débutants)

 

 

PROBLÈME DE L'ÉCHIQUIER TRONQUÉ

 

Problème

 

*    Peut-on couvrir un échiquier tronqué de deux cases de même couleur 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 opposés ont été 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é.

 

Historique

*    Le problème de l'échiquier tronqué (mutilated chessboard problem) a été proposé par le philosophe Max Black dans son livre Critical Thinking (1946).

*    D'autres l'ont repris par la suite: Solomon W. Golomb (1954), Gamow & Stern (1958) ou par Martin Gardner dans Scientific American – Mathematical Games.

 

Théorème de Gomory

*    Il traite le cas où les cases retirées sont de couleurs différentes

*    Alors, il y a toujours une solution.

*    Prouvé par Ralph E. Gomory en 1973.

 

 Voir Dualité / Brève 572 / Tétris et pavage

 

 

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 (débutants)

*         Voir haut de page

Voir

*         Intelligence artificielle

*         Jeux et énigmes – Index

*         Pentominos

*         Polyominos

Site

*         Covering A Chessboard With Domino – Cut The Knot

*         Covering a chessboard with dominoes – Eight problems

*         Domino tiling – Wolfram MathWorld

*         OEIS A00403 – Number of domino tilings (or dimer coverings) of a 2n X 2n square

Cette page

http://villemin.gerard.free.fr/Puzzle/EchecPav.htm