Les problèmes de pavage et de coloriage sont souvent liés. Il arrive en particulier qu'un coloriage habile permette de montrer qu'un pavage est impossible ou au contraire indique comment paver une figure.
Si on se donne un échiquier ou plus simplement une grille de huit cases de hauteur et huit cases de largeur, et qu'on retire deux cases. On peut se demander, en toute généralité si on peut la recouvrir de dominos (des rectangles d'une case de large et deux cases de haut).
Pour y répondre, la premiére chose à faire est de colorier la grille, c'est-à-dire de prendre un échiquier ! Comme les dominos seront posés sur deux cases de couleurs distinctes, ils recouvriront une surface ayant le méme nombre de cases de chaque couleur. On en déduit que le pavage est impossible lorsque les deux cases otées sont de même couleur.
On dessine maintenant un serpentin sur l'échiquier, c'est-à-dire un chemin (d'une case de large) qui parcourt tout l'échiquier. Il alterne évidemment cases blanches et cases noires : le serpentin est formé de segments horizontaux ou verticaux, mais pas diagonaux. Si on retire deux cases de couleurs distinctes, cela coupe le serpentin. Si les deux cases étaient consécutives sur le serpentin, on a un seul morceau. Sinon, on a deux morceaux. Puisque les cases retirées sont de couleurs différentes, tous les morceaux de serpentin qu'on a se terminent par une case de couleur différente de celle de la case par laquelle ils commencent. On peut donc les paver chacun avec des dominos.
En résumé, un échiquier privé de deux cases est pavable par des dominos si et seulement si les deux cases sont de couleurs différentes.
En ce qui concerne les triominos, en forme de L (ou un carré de deux cases de côté auquel on a enlevé un carré d'une case de côté), il est facile de paver l'échiquier privé d'un coin. En effet, on ferme le coin avec un triomino et on décompose ensuite ce qui reste en deux rectangles 6x2 et un carré 6x6. Ce carré est en fait formé de trois rectangles 6x2. Et un rectangle 6x2 est la réunion de deux rectangles 3x2. Par conséquent il nous suffit de constater qu'un rectangle 3x2 est la réunion de deux triominos pour paver notre échiquier.