Enigmo 1 : Périmètre minimum

Posté par matovitch matovitch

Voici une adresse interessante : http://fr.wikipedia.org/wiki/Polyomino

PS : ça va être dur très dur !!!

Posté par rogerd rogerd

Bonjour à tous!
J'ai à peu près fini mon programme Maple.
Comme déjà dit: un contour est défini par une suite d'actions:
+1="tourner à droite",  0="aller tout droit", -1="tourner à gauche".
J'utilise 6 formes élémentaires: les 4 qui sont données et les pièces 2 et 4 retournées.
Quand on lui donne 2 formes, élémentaires ou composites, et qu'on lui impose la longueur de la frontière commune,  le programme sait construire la suite des assemblages possibles de ces deux formes en précisant pour chacun le point de départ (dans la liste associée) de la frontière commune. C'est indispensable si l'on veut un dessin où l'on voit les 2 formes accolées.
Je me suis arrangé pour ne pas avoir à construire des assemblages où la frontière commune ait une longueur<3, car ils risquent d'être trop nombreux et demander un temps non raisonnable.
A partir de là,  j'ai fait des expériences, continuant d'écrire le programme au fur et à mesure des conclusions.
Pour chaque expérience, Maple travaille pendant un temps imperceptible.
En gros:je fais l'hypothèse (absurde?) qu'il y a un périmètre<34; j'assemble 2 formes, puis j'accole la 3°, puis la 4°, en faisant les dessins au fur et à mesure.
J'arrive toujours à une impossibilité.
Il me reste à examiner le cas, peu vraisemblable , où 2 formes, élémentaires ou composites, auraient 2 frontières communes de longueur<3, et où on pourrait loger le reste dans le trou ainsi formé.
Je pense régler ce cas bientôt et prouver ainsi que
le périmètre minimum est bien 34.

Je suis à votre disposition pour toute précision.
Je peux même fournir le programme Maple. Cela me rassurerait que quelqu'un vérifiât mes allégations! (bien dit, n'est-ce pas?)

A bientôt!

Posté par veleda veleda

bonjour et bravorogerd
quel travail,je suis en admiration et me voilà rassurée,le minimun est bien 34

Posté par matovitch matovitch

Bonjour !
Question toute bête : Combien de possibilité avec les frontière communes de longueur <3 (avec ces 4 pieces) ?

Posté par rogerd rogerd

Bonsoir matovitch!

Si tu parles d'assemblages où deux pièces élémentaires ont une frontière commune de longueur<3, il y en a certainement beaucoup et le programme exploserait sans doute si je lui demandais.
Mais le problème qui me reste à régler n'est pas celui -là:
Il me faut chercher les couples d'assemblages (1 pièce élémentaire+ 1 pièce élémentaire) ou (assemblage de 2 piéces élémentaires + 1 pièce élémentaire) qui se jouxtent suivant deux frontières communes ayant chacune une longueur<3 (ménageant ainsi un trou susceptible de recevoir ce qui manque).
Il ne doit pas y en avoir beaucoup et je pense y arriver.

Merci pour toute remarque comme la tienne, qui me force à creuser encore le problème.

Posté par veleda veleda

bonjour rogerd
désolée,j'ai mal lu la fin de ton post du 02 22h38,désolée pour toi que ce ne soit pas tout à fait terminé et merci pour tout le temps que tu passes pour trouver que 34 est bien le minimun
bonne journée

Posté par rogerd rogerd

Bonjour à tous et à toutes.

Je pense finir le travail en ne faisant pratiquement pas appel au programme Maple.
Pointons du doigt le raisonnement à préciser:
Tout est basé sur la formule: périmètre d'un assemblage= 66-2*S où S est la somme des longueurs des frontières communes à 2 pièces. 66 est la somme des périmètres des 4 formes (20+14+20+12).
D'autre part, pour faire un assemblage, je pars d'une pièce, lui en accole une 2°, puis une 3°, puis une 4°.  Pour calculer la longueur de la frontière commune à la nouvelle pièce B et à l'assemblage déjà fait A, je considère que la frontière commune à A et B est d'un seul tenant.
Il me faut prouver que l'autre cas, où A et B isolerait donc un trou ne peut pas se produire.
Déjà, si B est la dernière pièce, et si trou il y a, on ne peut le boucher.
Supposons donc que A est formée de 1 ou 2 pièces et qu'il y a un trou entre A et B.
On peut essayer de le boucher avec un assemblage de 2 pièces, qui aura un périmètre minimum de 27 (20+12-5). Ca ne marchera pas, le contact entre une pièce du trou et une pièce du bord ayant une longueur maximale de 5.
Même raisonnement si on essaie de boucher le trou avec une seule pièce, de périmètre 20.
Même raisonnement  si A est formée d'une seule pièce et qu'on essaie de boucher le trou entre A et l'autre pièce (B) avec une seule pièce.
Reste à examiner le cas où A est formée de 2 pièces et qu'on essaie de caser , dans le trou ménagé par A et B, la dernière pièce, de périmètre 12 ou 14.
Compte tenu du fait que la frontière entre 2 pièces est de longueur 5 au maximum, cela fait peu de cas à envisager. On examine alors les configurations données par le programme avec ces contraintes . Ces configurations ont déjà été préparées. On voit qu'aucune ne marche.
Si je n'ai pas fait de faute, ni dans mon raisonnement, ni dans mon programme (qui, suivi pas à pas, semble bien fonctionner):
Le périmètre minimum est bien de 34
  

Posté par gui_tou gui_tou

Bonjour,

Quelle perspicacité rogerd !

Posté par mikayaou mikayaou

en effet gui-tou, salut !

je sens rogerd bientôt futur étoilé, frenicle et no_futur2 ont à bien se tenir...

Posté par gui_tou gui_tou

Salut Mika ! Quant à toi, très belle démo pour l'énigme du camion !

Posté par mikayaou mikayaou

merci gui-tou

en revanche j'aurais mérité un car je n'ai pas vu la subtilité de la distance max et j'ai arrondi mal à propos...

monrow a été sympa sur ce coup là

anw, ou , je ne participe que rarement et la sanction a peu d'importance