Périmètre de trois polyominos

Domi

Bonjour à tous :-D

Une question bête que je me suis posée en cherchant un problème que je vous soumettrai plus tard .

On peut facilement assembler deux polyominos identiques de façon à ce que le périmètre de la figure formée par l’ensemble soit inférieur à celui de l’un d’entre eux ( avec une spirale par exemple ) .

Avec le même principe on peut assembler trois triominos et obtenir le même résultat .

Mais peut-on réaliser la même chose avec trois polyominos ?

Il y a peut-être deux variantes selon que l'’on accepte les symétries axiales ou pas .

Merci d’avance pour vos réponses .

Domi

Domi

Un ensemble de quatre polyominos identiques dont le périmètre est inférieur à l'un d'entre eux , il ne passionne pas les foules ce problème :-D

Domi

Dom

À vrai dire j'ai voulu chercher un peu lors du premier message.
Mais j'ai oublié de poser une question : qu'appelle-t-on "polyominos" exactement ?

Domi

C'est un polygone constitué de carrés identiques et dont la frontière est un lacet simple .

Domi

b.b

Je ne suis pas sûr d'avoir bien compris l'énoncé, cette figure convient-elle ?
Le fond noir est un peu moche... je ne sais pas comment corriger ça.

[Peut-être comme ça ? ;-) AD]

GaBuZoMeu

Pas très identiques.

b.b

Ah oui, effectivement...

Domi

Le problème qui m'a inspiré s'interroge sur la construction assez surprenante de Voderberg : un polygone peut être complètement cerné par deux copies de lui même ( sans contact excepté de sommet à sommet ) et en plus le périmètre de l'enveloppe est égal au périmètre d'une seule pièce .

La réalisation du même exploit avec un polyomino semble inconcevable , elle l'est certainement s'il n'y a pas de solution à la question initiale .

Domi

b.b

@AD
Merci pour la correction.
[À ton service :-) AD]
@Domi
Je tente de prouver qu'il est impossible d'obtenir un rectangle à l'arrivée. Je ne sais pas si c'est une bonne piste de réflexion, mais pour le moment, j'ai essayé d'associer un graphe non orienté au polyomino ainsi qu'au rectangle pour trouver des inégalités restrictives sur les arêtes ou les sommets.

Domi

J'étais plutôt parti sur un codage du type GHGBBDDH du polyomino avec quelque règles simples :

- On tourne dans le sens trigo .
- On n'a jamais deux voisins H et B ou G et D .
- Le nombre total de H est égal au nombre total de B et de même pour les G et les D .
- Pour éviter les contacts , la troisième règle n'est réalisée pour aucune sous suite .

Il y a autant de représentations du polyomino que de sommets ( en changeant le point de départ ) .

Cette représentation a l'avantage de transformer le problème en concaténations de mots avec disparition des inverses .

Les trois polyominos sont ( à une translation près ) les images du modèle par l'une des huit transformations laissant le carré invariant . Le contact entre les pièces se fait entre deux mots inverses par exemple HDDHGHG se frottera à DBDBGGB qui fera disparaître les deux chaînes sur le périmètre de l'ensemble .

On est en fait ramené à chercher un mot ( polyomino ) M , deux transformations f et g du groupe diédral d'ordre 8 et trois chaînes a , b et c tels que :

$M=xc\bar{b} , f(M)=ya\bar{c} \text{ et } g(M)=zb\bar{a}$ .

La longueur totale $a+b+c$ devant être supérieure ( ou égale ? ) à celle de M .

Je ne suis pas convaincu que tout cela rende les choses plus claires :-D

On peut sans doute faire une recherche informatique , mais s'il n'y a pas de solution :-S

Domi

b.b

Bonsoir Domi

Pour être sûr de bien comprendre, comment codes-tu le tétromino suivant ?

Domi

En partant du sommet en haut à droite : GBGBDDDHGH .

Domi

b.b

D'accord, je comprends mieux, merci. J'avais cru à tort que tu te donnais un carré au départ et que chaque pas dans une direction correspondait à un carré adjacent.

De mon côté, je n'ai rien trouvé avec les graphes, ça doit être une fausse piste.

Clydevil

@Domi: Je pense qu'on peut trouver un meilleur codage (haut bas gauche droit présente un hardcode qui pollue le problème) par exemple coder les virages relativement au parcourt sur le périmètre. pour le GBGBDDDHGH ci dessus ça donnerait:
1g1d1g1g3g1g1d1g (les chiffres donnent un nombre d’unités ou on avance, les lettres représente les virages, on part ici du même coin avec une orientation initiale horizontale vers la gauche de l'image, les virages sont relatifs au chemin qu'on prend en suivant le contour)

L’intérêt de ce codage est que la condition pour coller un morceau de périmètre a un autre (d'une copie du polyomino) s’écrit pareil qq soit la rotation/l'orientation de celui ci (parce que le codage ne depend pas de l'orientation du polyomino). Par exemple pour le debut du contour (1g1d1g1) il suffit d'avoir sur le contour ailleurs cette même séquence à l'envers et en dualisant les virages c'est a dire 1d1g1d1 et si on la trouve on peut la faire coïncider a la première.

En espérant que ça apporte de l'eau au moulin!

Domi

Bonjour Clydevil , tu as certainement raison .

En fait je n'ai pas développé cette idée car je ne crois pas la réalisation possible . Je ne dis rien de transcendant en rappelant que la parité joue un rôle essentiel , en empilant des rectangles spiralés suffisamment longs comme dans le message initial , on peut réussir l'exploit avec tout nombre pair de polyominos .

Je n'ai pas trouvé un seul exemple qui fonctionne avec un nombre impair de polyominos :-S

Domi