12 novembre 2021

2 messages - Retourner à l'article
  • Novembre 2021, 2e défi

    le 12 novembre 2021 à 08:48, par Al_louarn

    Aux symétries près, il n’existe que deux configurations de $3$ petits carrés reliés par leurs côtés (triominos) : en « L » ou en « I ». Dans les deux cas, il y a un et un seul petit carré relié aux deux autres, que nous appellerons centre du triomino. Il suffit donc de compter, pour chaque petit carré de la grille, le nombre de triominos dont il est le centre. Et pour un carré de degré $d$ (càd relié à $d$ autres carrés dans la grille), c’est simplement le nombre de façons de choisir $2$ carrés parmi $d$, soit $\binom{d}{2}$. Comme la grille est composée de $4$ carrés de degré $2$, $4$ carrés de degré $3$ et $1$ carré de degré $4$, le nombre total de triominos est $4\binom{2}{2} + 4\binom{3}{2} + 1\binom{4}{2} = 4 \times 1 + 4 \times 3 + 6 = 22$

    On généralise facilement à une grille $n \times n$ (pour $n \geq 2$). Comme il y a $4$ carrés de degré $1$, $4(n-2)$ carrés de degré $3$ et $(n-2)^2$ carrés de degré $4$, le nombre total de triominos est $4 + 12(n-2) + 6(n-2)^2 = 4 + 6n(n-2)$.

    Beaucoup plus difficile : compter les quadriminos sur une grille $4 \times 4$, puis sur une grille $n \times n$...

    Répondre à ce message
    • Novembre 2021, 2e défi

      le 12 novembre 2021 à 10:56, par Al_louarn

      Je trouve $113$ quadriminos sur la grille $4 \times 4$ et $19n^2 -56n + 33$ sur la grille $n \times n$.
      L’idée est d’insérer chaque quadrimino dans un rectangle aussi petit que possible, ce qui me donne les rectangles $1 \times 4$, $2 \times 2$ et $2 \times 3$. Il faut alors compter le nombre façons de placer un quadrimino dans chaque type de rectangle et multiplier par le nombre de façons de placer ce rectangle sur la grille.
      Pour les rectangles $1 \times 4$ et $2 \times 2$, il n’y a qu’un seul quadrimino possible puisqu’ils sont formés de $4$ petits carrés.
      Pour le rectangle $2 \times 3$ c’est plus délicat. Il s’agit d’exclure $2$ des $6$ petits carrés, ce qui donne $\binom{6}{2} = 15$ possibilités, mais il faut en exclure $5$ qui ne donnent pas une figure connexe, et $2$ qui correspondent au quadrimino $2 \times 2$ qui est déjà compté dans le « rectangle » $2 \times 2$. Ce qui nous donne $8$ configurations acceptables pour le rectangle $2 \times 3$.
      Ensuite, le nombre de rectangles $i \times j$ dans la grille $n \times n$ est $(n-i+1)(n-j+1)$, mais il faut encore multiplier par $2$ si $i \neq j$ car on peut les placer horizontalement ou verticalement.
      Au final on obtient $2n(n-3)$ pour le carré $1 \times 4$, $(n-1)^2$ pour le carré $2 \times 2$, et $16(n-1)(n-2)$ pour le carré $2 \times 3$, ce qui fait un total de $19n^2 -56n + 33$.

      Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.