polymino

Imaginez cinq carreaux carrés identiques posés sur une grille. Chaque nouveau carreau doit partager un côté entier avec au moins un carreau déjà placé. L'ensemble obtenu est un polymino d'ordre 5, donc un pentomino.

Tourner ou retourner l'assemblage ne crée pas ici une nouvelle figure. Seule compte la manière dont les carrés sont reliés. En revanche, deux carrés qui se touchent seulement par un coin ne sont pas côte à côte au sens de la définition.

Un polymino, aussi appelé polyomino, est l'union d'un nombre fini de carrés congruents, reliés de proche en proche par des côtés entiers. Des carrés congruents ont la même taille et la même forme. L'ordre, noté ici n, est exactement le nombre de carrés de l'assemblage. Le terme a été introduit en 1953 par Solomon W. Golomb.

Dans la convention retenue par la définition source, deux assemblages représentent le même polymino si une rotation ou une réflexion permet de les faire coïncider. Une translation ne change que leur position dans le plan. Pour comparer deux figures, il faut vérifier que toute la disposition géométrique de leurs carrés coïncide après l'une de ces transformations. Les contacts entre carrés ne sont qu'un contrôle complémentaire, car ils ne déterminent pas toujours la forme.

Les noms suivent l'ordre : monomino pour n = 1, domino pour n = 2, triomino ou trimino pour n = 3, puis tétromino, pentomino, hexomino, heptomino, octomino, nonomino et décamino pour les ordres 4 à 10. Les figures avec un trou intérieur restent admises dans le dénombrement. Le nombre de formes distinctes augmente rapidement avec l'ordre, sans formule générale connue à ce jour pour le calculer.

Construisons une figure sur une grille. Les données sont cinq carrés identiques, repérés A, B, C, D et E. A et B occupent la rangée du bas ; C et D sont juste au-dessus ; E est placé au-dessus de C. Chaque carré a donc au moins un côté entier commun avec le reste de l'assemblage.

1. Comptez les carrés : A, B, C, D et E donnent 5.
2. Suivez les contacts par côtés : E touche C ; C touche A et D ; D touche B ; A touche B.
3. L'assemblage est donc relié de proche en proche.
4. Son ordre vaut 5 : c'est un pentomino.

La figure associée montre aussi le même assemblage après un quart de tour. Pour contrôler le résultat, recomptez cinq carrés dans chaque dessin, puis faites mentalement pivoter tout le dessin d'un quart de tour et vérifiez que chacun des cinq carrés, avec sa lettre, se superpose à sa position dans l'autre dessin. La conservation des contacts entre lettres complète ce contrôle, mais ne suffit pas à elle seule. La rotation change la présentation, mais pas le polymino selon la convention retenue.

Pour classer un assemblage, comptez d'abord ses carrés. Cinq carrés conduisent au nom pentomino ; quatre conduisent au nom tétromino. Ce comptage donne l'ordre, mais ne suffit pas à identifier la forme.

Pour décider si deux dessins représentent la même forme, essayez de faire coïncider leurs carrés par translation, rotation ou réflexion. Vérifiez que chaque carré se superpose effectivement à un carré de l'autre dessin, avec les mêmes positions relatives ; les contacts par côtés servent de contrôle complémentaire. Si toute la disposition coïncide, gardez un seul représentant dans le dénombrement.

Pour tester une figure candidate, partez d'un carré et passez de carré en carré uniquement par des côtés entiers. Si certains carrés restent inaccessibles, l'ensemble ne forme pas un polymino unique ; il faut traiter ses assemblages séparément.

Polymino et polygone. Un polygone est délimité par des segments, sans devoir provenir de carrés identiques. Un polymino exige au contraire une décomposition en carrés congruents joints par des côtés entiers. Une forme triangulaire est un polygone, mais pas un polymino.

Ordre et nombre de formes. L'ordre compte les carrés d'un seul polymino ; le dénombrement compte les polyminos distincts d'un ordre donné. La figure de l'exemple a ainsi l'ordre 5, ce qui ne donne pas à lui seul le nombre de pentominos possibles.

Contact par un coin. Si deux groupes de carrés ne se rencontrent qu'en un sommet, aucun côté entier ne les relie. Le symptôme est qu'un parcours de carré en carré par les côtés ne peut pas atteindre tout l'ensemble. Il faut alors compter plusieurs assemblages, pas un seul polymino.

Orientation trompeuse. Deux dessins peuvent sembler différents parce que l'un est tourné ou réfléchi. Avant de les compter séparément, essayez toutes les rotations et un retournement, puis comparez les contacts. Dans la convention de cette fiche, une coïncidence signifie qu'il s'agit du même polymino.

Trou intérieur. La présence d'une région vide entièrement entourée ne retire pas la figure du dénombrement. Il faut compter seulement les carrés qui composent l'assemblage, pas les cases vides du trou. Même avec un trou, l'ordre reste donc le nombre de carrés présents.

Le tétramino permet d'étudier en détail le cas d'ordre 4 et de comparer plusieurs contacts entre quatre carrés.

Le pentamino prolonge directement l'exemple de cinq carrés et affine l'étude des formes d'ordre 5.

Ces cas particuliers montrent pourquoi le dénombrement demande deux contrôles successifs : construire des assemblages valides, puis éliminer ceux qui coïncident après rotation ou réflexion.