Dénombrement de carrés (cas particulier)

[moebius2]

Bonjour,

Je me demande s'il existe une formule/méthode pour calculer tous les carrés visibles sur une figure particulière.

Par exemple, pour un carré "régulier" de coté 3 (figure 1 de la PJ), on dénombre au total 3*3+2*2+1=15 carrés. La formule est connue et il n'y a pas de problème dans ce cas.

Mais qu'en est-il pour la figure 2 ? Si je compte bien il y a 27 carrés, mais est-ce qu'il existe une formule ou méthode pour trouver ce nombre ? Notamment pour des cas avec beaucoup de petits carrés où le comptage à la main n'est pas possible.

Merci
-----

[gg0]

Bonjour.

Je ne crois pas trop à une formule utilisable dans tous les cas. Et de plus il faut savoir additionner : 3*3+2*2+1=15 est faux

Cordialement.

[epiKx]

Bonjour, je suis plutôt d'accord avec gg0, pas de formule générale...
Toutefois, notons N le nombre cherché. Pour des figures du type de la figure 1, i.e un carré de côté n (où n entier naturel non nul, en considérant que les petits carrés composant la figure sont de côté 1) , on a une formule remarquable semble-t-il:

(pour la vérifier, compter le nombre de carrés de côtés k pour k variant de 1 à n). Définissons ensuite la "taille de jonction" (en abrégé tj) de 2 figures géométriques composées de petits carrés de côtés 1: c'est la longueur maximale d'1 chemin (trait continu) délimitant les 2 figures.
Alors: en notant N1, N2 le nombre de carrés des 2 figures,
*si tj=1 alors N=N1+N2
*si tj=2 alors N=N1+N2+j où j est le nombre de chemins de longueur 2 délimitant les 2 figures.
*si tj>=3 alors :

où r est le nombre de chemins différents entre les 2 figures, est le nombre de carrés qui comportent des carrés de côté 1 présents à la fois dans les 2 figures, contenant au moins un segment de longueur 1 du chemin k correspondant.
Je propose donc la méthode de comptage suivante: partitionner la figure de manière à faire apparaître le maximum de figures de formes carrées (puisque l'on connaît alors la formule) et de taille maximale (tant qu'à faire), possédant des tailles de jonction minimales entre elles 2 à 2. On compte alors le nombre de carrés dans chacune des figures de la partition. Notons F1,..., Fp les figures composant la partition.
Soit E 1 ensemble de figures initialement vide.
On débute alors le comptage: on part d'1 figure quelconque notée F1: E=F1.
On ajoute alors les figures F1,...,Fp une par une à E en mettant à jour à chaque fois le nombre de carrés, en suivant les règles des tailles de jonction plus haut. Si une taille de jonction est supérieure à 3 : il suffit de compter à chaque fois le nombre de carrés de longueur k (k variant de 1 à m où m est à définir) qui comportent des carrés de côté 1 présents à la fois dans les 2 figures.
Ainsi, dans la figure 2, j'ai partitionné en faisant apparaître un carré de côté 2 et un autre de côté 3.
En appliquant cette méthode, j'ai obtenu N=14 (carré de côté 3) + 5 (carré de côté 2) + 2 + 2 + (2 + 1) (jonction de taille 2) = 26 carrés.
En espérant t'avoir aidé,
epiKx.

[epiKx]

Pour être complet, je vous propose une 2ème méthode, beaucoup plus longue et pratiquement inutilisable à la main, mais qui se programme plus facilement que la précédente. On représente la figure géométrique formée de petits carrés de côté 1 sous la forme d'1 matrice (tableau de nombres). Ce tableau est de taille n*n où n est le côté du plus grand carré qui peut contenir la figure. Le coefficient (i,j) de cette matrice vaut 1 si la case correspondante de la figure est recouverte d'1 petit carré de côté 1 et 0 sinon. Ensuite, il suffit de parcourir tous les petits carrés de côtés 1 de la figure et de compter pour chacun le nombre de carrés de côté k (pour k variant de 1 à n) que vous pouvez former avec ce petit carré situé à l'extrémité haut-gauche du carré de côté k. En additionnant les termes obtenus, vous avez votre nombre.
Cordialement,
epiKx.

[A voir en vidéo sur Futura]

[moebius2]

Merci epiKx. Tes réponses m'aident en effet. L'idée de la matrice me plaît bien, je vais voir si je peux en faire quelque chose.
Cdt