Nombres de zones (maximum 3x3) dans une grille — Les-mathematiques.net The most powerful custom community solution in the world

Nombres de zones (maximum 3x3) dans une grille

Bonjour :smile:
Soit n et m 2 entiers supérieurs ou égaux à 3. Dans une grille rectangulaire composée de $n \times m$ cases, combien y a-t-il de zones ? Sachant qu'une "zone" est n'importe quelle association de cases qui tient dans un carré de taille 3x3. Pour illustrer, voici quelques exemples de zones valides (non exhaustifs) : chaque couleur est une possibilité.
Attention de ne pas compter 2 fois la même zone par translation.
PS : ceci n'est pas un exercice mais une quantité dont j'ai eu besoin. J'aimerais comparer avec les amateurs de dénombrement. Je repasserai poster ma réponse.
Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.

Réponses

  • Modifié (June 2023)
    Bonjour
    Par translation, ou pour toutes les symétries ? Si j'étais vous je regarderais du côté du lemme de Burnside. 
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Modifié (June 2023)
    Bonjour
    Ce n'est pas très élégant mais, comme il y a $2^9 = 512$ possibilités, rien n'empêche de toutes les énumérer et les comparer avec un programme. Mais ce genre de technique s'arrêtera vite en augmentant la taille de la grille...
  • Modifié (June 2023)
    Bonjour,
    J'ai cru comprendre qu'une "zone" est une partie non vide  de l'ensemble des $mn$ cases susceptible d'être "contenue dans un  carré $3\times 3$".
    Je dis qu'une zone est "de format $x \times y$"( $(x,y)\in[\![1;3]\!]^2$) si le rectangle de dimensions minimales qui la contient est un rectangle $x\times y. $
    Pour un rectangle $x\times y$, je note $N_{x\times y}$ le nombre de zones de format $x\times y$ qu'il contient. Ainsi:
    $N_{1 \times1} =N_{1\times 2} =N_{2\times 1}=1, \quad N_{1\times 3} =N_{3\times 1}=2, \quad N_{2\times 2} =7,\quad N_{2\times 3} =N_{3\times 2} =32,\quad N_{3\times3}  =322.$
    Le nombre de rectangles $x\times y$ contenus dans un rectangle $m\times n $ est $ (m+1-x) (n+1-y). \:\:$Le nombre de "zones" est donc:
    $$\boxed{\mathcal N_{m\times n}=\displaystyle\sum_{1\leqslant x,y\leqslant 3}(m+1-x)(n+1-y)N_{x\times y}=400mn-752(m+n)+1423.}$$
  • Modifié (June 2023)
    Bravo Lou16. Tu es toujours au top. J'ai fait le même raisonnement, et obtenu le même résultat.
    Si m=n, alors le premier terme ressemble à un carré parfait, et le second terme à un double produit. Pourtant, cela ne coïncide pas. Et dans le même temps, les valeurs sont suffisamment proches pour que les nombres de la formule finale soient petits :
    $\mathcal N_{n\times n}= (20n)^2-2*752*n+1423 = (20n-38)^2+16n-21$.
    Application numérique : $\mathcal N_{50\times 50}= 926223$, soit un petit million de zones, manipulables par un ordinateur moderne.
    Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!