Polyominos

Des formes quadrillées à recouvrir exactement, du rectangle à la forme trouée, en faisant glisser des pièces. Le but : y parvenir avec le moins de pièces possible, parmi celles qui sont proposées. D'autres défis imposent un seul type de pièce, ou une liste comme les douze pentominos. Les coloriages et la récurrence disent quand un pavage est impossible, et quand il existe toujours.

On recouvre une forme quadrillée (rectangle, rectangle troué, escalier, croix ou forme tirée au hasard) avec des polyominos que l'on fait glisser, tourner et retourner. Le défi d'ouverture, « type TFJM² de Marie », donne six pièces à volonté (monomino, domino, tromino droit, tromino en L, tétromino en T, pentomino en X) : il s'agit de recouvrir la forme avec le moins de pièces possible, et la page compare votre résultat au minimum, qu'elle a cherché ($7$ pièces pour un rectangle de $5 \times 5$, $10$ pour $6 \times 6$, $16$ pour $8 \times 8$). Trois autres familles de défis : un seul type de pièce, toutes les pièces de $3$, $4$ ou $5$ cases, ou une liste dont chaque pièce sert une fois. Chaque forme proposée a été pavée par la page avant d'être affichée.

Ce que cela signifie : la page énumère les polyominos à rotation et retournement près et en trouve $1$, $1$, $2$, $5$, $12$, $35$ et $108$ pour $1$ à $7$ cases. Que l'aire soit un multiple de la taille des pièces est nécessaire, et loin de suffire : par un coloriage en damier, les cinq tétrominos ne pavent aucun rectangle, le tétromino en T couvrant trois cases d'une couleur et une de l'autre. À l'inverse, une récurrence montre qu'un carré de côté $2^n$ privé d'une case quelconque se pave par des trominos en L. Les douze pentominos pavent le rectangle de $6 \times 10$ de $2\,339$ façons et celui de $3 \times 20$ de $2$ façons seulement (résultats admis, obtenus par ordinateur).

Le piège le plus courant est de conclure qu'une forme est pavable dès que son aire s'y prête : le carré de $6 \times 6$ a $36$ cases et ne peut pas être pavé par des tétrominos en T.