Dominos sur l'échiquier

Recouvrir de dominos un échiquier auquel on a retiré deux cases. Avec deux coins opposés en moins, c'est impossible, et il suffit de compter les couleurs pour le démontrer ; avec une case de chaque couleur en moins, c'est toujours possible.

Sur un plateau de $2$ à $8$ lignes et colonnes, entier ou privé de deux cases, on pose des dominos qui couvrent chacun deux cases voisines. La page compte les cases libres de chaque couleur, signale l'impasse quand il ne reste plus deux cases voisines, et répond sur demande à la question « est-ce possible ? » en cherchant un couplage parfait.

Ce que cela signifie : un domino couvre une case claire et une case foncée, donc un plateau pavé en a autant de chaque sorte ; la différence entre les deux compteurs est un invariant. L'échiquier de $8$ sur $8$ privé de deux coins opposés garde $30$ cases d'une couleur et $32$ de l'autre : aucun pavage n'existe. Si l'on retire une case de chaque couleur, le pavage existe toujours (théorème de Gomory, admis dans la page). L'échiquier entier admet $12\,988\,816 = 3\,604^2$ pavages, nombre que la page recalcule.

Le piège le plus courant est de croire qu'on a presque réussi : après $30$ dominos, il reste deux cases de même couleur, et aucune habileté n'y changera rien. À l'inverse, un décompte équilibré est nécessaire, mais ne suffit pas en général.