Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 31

Tetraminos



  1. #1
    Médiat

    Tetraminos

    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

    -----

    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  2. Publicité
  3. #2
    Médiat

    Re : Tetraminos

    Si c'est trop compliqué, on peut commencer avec 4 tétraminos et augmenter au fur et à mesure.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    LeMulet

    Re : Tetraminos

    Citation Envoyé par Médiat Voir le message
    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)
    Bonjour, et Merci.

  5. #4
    Médiat

    Re : Tetraminos

    Attention, ici les rotations sont interdites, par conséquent (par exemple) la barre horizontale et la barre verticale sont deux tétraminos différents
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  6. #5
    LeMulet

    Re : Tetraminos

    Citation Envoyé par Médiat Voir le message
    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
    Bonjour, et Merci.

  7. A voir en vidéo sur Futura
  8. #6
    Médiat

    Re : Tetraminos

    Non, 19 :
    Z R180 = Z
    Z-R270 =
    Z-R90

    même chose pour S
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  9. Publicité
  10. #7
    Verdurin

    Re : Tetraminos

    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.

  11. #8
    Médiat

    Re : Tetraminos

    Citation Envoyé par Verdurin Voir le message
    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 ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  12. #9
    Verdurin

    Re : Tetraminos

    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.

  13. #10
    Médiat

    Re : Tetraminos

    Citation Envoyé par Verdurin Voir le message
    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 !
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    Verdurin

    Re : Tetraminos

    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.

  15. #12
    Médiat

    Re : Tetraminos

    Citation Envoyé par Verdurin Voir le message
    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  16. Publicité
  17. #13
    Verdurin

    Re : Tetraminos

    En effet, j'avais oublié ce cas.

  18. #14
    obi76

    Re : Tetraminos

    Citation Envoyé par Médiat Voir le message
    Je confirme.

    Par conte avec 8 I il faut un carré de coté 8
    Pourtant j'y arrive en 6... o_O
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  19. #15
    Médiat

    Re : Tetraminos

    En les tordant un peu (ou en utilisant 4 I et 4 I R-90) ?
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #16
    obi76

    Re : Tetraminos

    Citation Envoyé par Médiat Voir le message
    En les tordant un peu (ou en utilisant 4 I et 4 I R-90) ?

    Même pas (ou alors j'ai mal compris)
    Images attachées Images attachées
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  21. #17
    Médiat

    Re : Tetraminos

    Ce ne sont pas des I mais des L et des J(plus ou moins tournés)
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #18
    obi76

    Re : Tetraminos

    Citation Envoyé par Verdurin Voir le message
    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 ?
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  23. Publicité
  24. #19
    Médiat

    Re : Tetraminos

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #20
    obi76

    Re : Tetraminos

    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à...
    Dernière modification par obi76 ; 04/05/2019 à 17h26.
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  26. #21
    Médiat

    Re : Tetraminos

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #22
    obi76

    Re : Tetraminos

    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é )
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  28. #23
    LeMulet

    Re : Tetraminos

    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 ?
    Bonjour, et Merci.

  29. #24
    Médiat

    Re : Tetraminos

    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).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  30. Publicité
  31. #25
    obi76

    Re : Tetraminos

    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 ?
    Images attachées Images attachées
    Paradoxalement, ce sont les débats stériles qui se reproduisent le plus.

  32. #26
    Médiat

    Re : Tetraminos

    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
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  33. #27
    LeMulet

    Re : Tetraminos

    Citation Envoyé par obi76 Voir le message
    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.
    Bonjour, et Merci.

  34. #28
    Verdurin

    Re : Tetraminos

    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.

  35. #29
    Verdurin

    Re : Tetraminos

    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.

  36. #30
    Médiat

    Re : Tetraminos

    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).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Sur le même thème :

Page 1 sur 2 1 DernièreDernière