Tetraminos

[Médiat]

Bonjour

Tout le monde connaît les tétraminos (4 carrés liés par au moins une face, tout se passe dans le plan).

Etant donné une liste de n tétraminos, on peut déterminer le plus petit carré dans lequel on peut les placer (éventuellement avec des trous), sans utiliser de rotations ou de symétries. Il y a une borne inférieure évidente : 2 racine(n).

Pourrez vous trouver les 10 tétraminos tels que ce carré minimal soit le plus grand possible …

PS : Je n'ai pas la réponse
-----

[Médiat]

Si c'est trop compliqué, on peut commencer avec 4 tétraminos et augmenter au fur et à mesure.

[LeMulet]

Si c'est trop compliqué, on peut commencer avec 4 tétraminos et augmenter au fur et à mesure.

C'est à peu près la même réponse de toutes façons avec 10 pièces ou 4 pièces; il faut employer les formes "les plus antagonistes" possibles.
Au jugé, sans vérifier... 2 O et 2 T.
(Nomenclature des pièces indiquée ici : https://fr.wikipedia.org/wiki/T%C3%A9tromino)

[Médiat]

Attention, ici les rotations sont interdites, par conséquent (par exemple) la barre horizontale et la barre verticale sont deux tétraminos différents

[A voir en vidéo sur Futura]

[LeMulet]

Attention, ici les rotations sont interdites, par conséquent (par exemple) la barre horizontale et la barre verticale sont deux tétraminos différents

D'accord, je n'avais pas bien intégré ce fait.
Donc pour cerner le problème, si je ne m'abuse, on a les 23 les pièces suivantes :
1.I
2.I-R90
3.O
4.T
5.T-R90
6.T-R180
7.T-R170
8.L
9.L-R90
10.L-R180
11.L-R270
12.J
13.J-R90
14.J-R180
15.J-R270
16.Z
17.Z-R90
18.Z-R180
19.Z-R270
20.S
21.S-R90
22.S-R180
23.S-R270

[Médiat]

Non, 19 :
Z R180 = Z

Z-R270 =

Z-R90

même chose pour S

[Verdurin]

Bonsoir,
avec une barre de 4 ( I ) et la même tournée d'un quart de tour il faut un carré de côté 5.

[Médiat]

Bonsoir,
avec une barre de 4 ( I ) et la même tournée d'un quart de tour il faut un carré de côté 5.

C'est le max min avec 2 tétraminos, mais avec 5 ou 10 ?

[Verdurin]

Trois tétraminos tiennent toujours dans un carré 5x5.

Avec quatre tétraminos il faut un carré plus grand : prendre quatre L qui nécessitent un carré de côté 6 ( sauf erreur de ma part ).

La suite me semble un problème de combinatoire assez difficile, mais il y a sans doute des idées que je n'ai pas encore aperçues.

J'y travaille.

[Médiat]

Avec quatre tétraminos il faut un carré plus grand : prendre quatre L qui nécessitent un carré de côté 6 ( sauf erreur de ma part ).

Cela me paraît correct

J'y travaille.

Bon courage !

[Verdurin]

Comme je manque de courage, je propose une conjecture :
huit tétraminos tiennent toujours dans un carré de côté 7.

Avec une remarque : si on prend huit L on ne peut pas les placer dans un carré de côté plus petit que 7.

Et j'espère que quelqu'un va réfuter cette conjecture.

[Médiat]

Avec une remarque : si on prend huit L on ne peut pas les placer dans un carré de côté plus petit que 7.

Je confirme.

Par conte avec 8 I il faut un carré de coté 8

[Verdurin]

En effet, j'avais oublié ce cas.

[obi76]

Je confirme.

Par conte avec 8 I il faut un carré de coté 8

Pourtant j'y arrive en 6... o_O

[Médiat]

En les tordant un peu (ou en utilisant 4 I et 4 I R-90) ?

[obi76]

En les tordant un peu (ou en utilisant 4 I et 4 I R-90) ?

Même pas (ou alors j'ai mal compris)

[Médiat]

Ce ne sont pas des I mais des L et des J(plus ou moins tournés)

[obi76]

Avec une remarque : si on prend huit L on ne peut pas les placer dans un carré de côté plus petit que 7.

Et j'espère que quelqu'un va réfuter cette conjecture.

Ben on parle bien de L là, non ?

[Médiat]

Deux choses :
1) Verdurin parle de L (tous les mêmes et pas un mélange de L et de J plus ou moins tournés)
2) Je répondais à la conjecture de Verdurin en donnant un contre exemple nécessitant un carré 8x8

[obi76]

Ha d'accord (la figure que j'ai montré peut cependant être facilement uniquement composée de L, plus ou moins tournés).

Cela dit je ne comprends quand même pas. On peut mettre 4 L dans un 4x4, 8L dans un 6x6. pourquoi dire qu'il faut un carré d'au moins 6x6 pour caser 4L et au moins 7 x 7 pour en caser 8... Je ne comprends plus rien là...

[Médiat]

En espérant être plus clair, voilà une solution avec que des L (J'ai mis le fond en jaune pour que ce soit plus lisible.

Image1.png

[obi76]

Ha OK, tous dans le même sens (c'est ce point de détail qui n'en est pas un qui m'avait échappé )

[LeMulet]

Mais on est bien d'accord, que lorsque vous cherchez à placer 10 pièces, les 10 pièces peuvent bien être choisies parmi les 19 types possibles ?
Ou alors les 10 pièces doivent toutes être de même type ?

[Médiat]

Oui on est d'accord, vous choisissez 10 pièces parmi les 19 types possibles (physiquement, vous disposez de 190 pièces (10 x 19) et vous en prenez 10 de votre choix).

[obi76]

Si j'ai bien compris, je vais tenter un truc.

4 pièces : 16 carrés, donc au plus petit un carré de racine(16) = 4 de côté.
5 pièces : 20 carrés, donc au plus petit un carré de racine(20) arrondi au dessus = 5 de côté.
6 pièces : 24 carrés, donc au plus petit un carré de racine(24) arrondi au dessus = 5 de côté.
7 pièces : 28 carrés, donc au plus petit un carré de racine(28) arrondi au dessus = 6 de côté.
8 pièces : 32 carrés, donc au plus petit un carré de racine(32) arrondi au dessus = 6 de côté.
9 pièces : 36 carrés, donc au plus petit un carré de racine(36) = 6 de côté.
10 pièces : 40 carrés, donc au plus petit un carré de racine(40) arrondi au dessus = 7 de côté.

J'ai bon ?

[Médiat]

Oui, pour n tétraminos, ils occupent 4n carrés unitaires il faut donc au moins un carré de côté 2 racine(n), et on peut trouver des exemples qui montre que ce minimum est atteint en choisissant bien les n tétraminos ; la question posée est de trouver le jeu ne 5 (ou 10,ou n) tétraminos tel que le plus petit carré qui les contient soit le plus grand possible, ou, ce qui est équivalent : quel est le plus petit carré qui peut contenir tous les jeux de 5 (ou 10, ou n) tétraminos

[LeMulet]

J'ai bon ?

Il y a de l'idée, mais tant qu'à faire, pour la dernière pièce, au lieu d'un I-R90, il vaudrait mieux rajouter un Z-R90.

[Verdurin]

Non.
On cherche un ensemble de n (en particulier n=10) tétraminos tel que le plus petit carré pouvant contenir ces n pièces soit le plus grand possible.

Je crois que le maximum est atteint pour n tétraminos identiques sauf pour n=2 et n=3.
Mais bien entendu une croyance n'a aucune valeur démonstrative.

[Verdurin]

En fait les à côtés de la questions sont intéressants :
dix tétraminos tiennent toujours dans un carré de côté 40.

D'après ce qui précède il existe un nombre n entre 8 et 40 tel que n'importe quel ensemble de dix tétraminos tiennent toujours dans un carré de côté n.
C'est évident si on est « platonicien ».
Ça l'est aussi si on ne n'est pas « platonicien » puisqu'il n'y a qu'un nombre fini ( mais grand ) de cas à examiner.

Mais le nombre n reste inconnu.

Je suis personnellement assez ignorant en logique et intuitivement « platonicien ».
Mais je me demande quel est le statut de n dans un cadre plus rigoureux.

[Médiat]

Bonsoir,

Je vous rassure, cette question n'a rien à voir avec Platon.

Je pense que votre borne sup peut être ramené à 9 sans trop d'efforts et en tout état de cause à 12 (immédiat).