Soit un damier de dimensions 10×10 auquel on a retiré la case du coin supérieur droit et celle du coin inférieur gauche. Est-il possible de couvrir le damier avec des dominos de dimensions 2×1 ?
Solution
Considérons que le damier est colorié comme c'est généralement le cas : une case sur deux est noire, et l'autre est blanche. Les deux cases du coin supérieur droit et du coin inférieur gauche sont de la même couleur (ici, noire). Après les avoir retirées, le damier comporte donc 48 cases noires et 50 cases blanches. Or, un domino recouvre nécessairement deux cases de couleurs différentes. Il n'est donc pas possible de recouvrir toutes les cases restantes avec des dominos.
Le même argument aurait fonctionné pour tout damier auquel on aurait retiré 2 cases de même couleur. À l'inverse, si l'on retire 2 cases de couleurs différentes, il est toujours possible de couvrir le reste du damier avec des dominos. Ce résultat est appelé théorème de Gomory (1973).
Aucun commentaire:
Enregistrer un commentaire