hier soir lors d'un repas ma sœur m'a posé le problème suivant :
On dessine un carré de 4 colonnes et 4 lignes à partir de carré de 1 fois 1.
Combien y a-t-il de carrés en tout ?
Après plusieurs tentatives et un dessin je trouve enfin la bonne réponse qui est 30. Je lui demande alors s'il existe un calcul qui généralise ce problème pour toutes les dimensions de carré ce à quoi elle répond négativement.
Comme je ne l'ai pas cru j'ai cherché et il apparaît que la solution est
$$\sum_{n=1}^{c}n^2$$
Où $c$ est la longueur des côtés du grand carré en longueur de côté de petit carré. En cherchant sur internet je retrouve cette même solution mais je me demande comment peut-on faire pour prouver que cela marche absolument tout le temps et si l'on ne peut pas aussi le généraliser pour toutes les dimensions (cube, hyper-cube, hyper-hyper-cube, etc)
J'ai peut être un truc qui passe avec une construction par récurrence :
Si l'on commence avec un carré de 1x1, on a 1 carré de 1x1.
Pour construire un carré de 2x2, on colle 3 carrés de 1x1 pour faire une forme de L et on y imbrique le carré d'avant. Cela fais 1 carré de 2x2 et $3+1 = 4$ carrés de 1x1.
Pour le carré de 3x3 on fait la même opération mais avec 5 carrés de 1x1. On a donc un carré de 3x3, 3 nouveaux carré des 2x2, un dans le coin et 2 sur les côtés soit 4 en tout et bien sûr 9 carrés de 1x1.
Pour le carré de 4x4 on a un nouveau carré de 4x4, 3 nouveaux de 3x3 soit 4 en tout, 5 nouveaux de 2x2 soit 9 et 7 nouveaux carrés de 1x1 soit 16.
Pour un carré de $n \times n$, on a un nouveau carré de $n \times n$, 3 nouveau de $(n-1) \times (n-1)$ ce qui en tout donne $3+1 = 4$, 5 nouveaux de de $(n-2) \times (n-2)$ soit $5+3+1 = 9$, etc.
On remarque que le nombre de carré de dimensions $(n-x)$ correspond la somme des $x+1$ premiers nombres impaires ce qui correspond à $(x+1)^2$. On a alors :
J'ai fait un petit tableau que j'ai envoyé sur Geogebra pour faire une analyse par curiosité.
Côté
Carrés
1
1
2
5
3
14
4
30
5
55
Après une analyse statistique à deux variables, il apparait que ça ressemble énormément à une fonction polynôme de degré 4. Étonnamment, le nombre $1/3$ y occupe une place prépondérante.
Sinon, je pense qu'une façon plus prosaïque d'aborder ce problème serait celle-ci.
Pour chaque "figure", on commence par compter le nombre de carrés de 1. Ensuite, on peut considérer que cette figure est une grille, et on peut alors compter tous les nœuds de cette figure, c'est à dire les points qui sont communs à quatre carrés. On a alors le nombre de carrés de 2.
On divise alors le nombre de points communs par quatre pour obtenir le nombre de carrés de 3. On fait de même avec les points communs aux carrés de 3 pour obtenir le nombre de carrés de 4, etc. Finalement, on arrive au grand carré.
Les "carrés de 1" sont les carrés rouges, le carré vert est un "carré de 2", etc.
Je vais essayer de mieux formuler mon propos et de faire un graphique. Mais pour ma part je trouve ce problème plus intuitif en le prenant comme ça.
@Rezemika : non : entre les carrés de taille 2x2 et ceux de taille 3x3, le ratio n'est pas de 4.
Pour compter le nombre de carrés de taille axa dans un carré de taille nxn, il faut (et il suffit de) compter le nombre d'emplacements possibles pour le sommet haut-gauche de notre carré axa.
@Rezemika : non : entre les carrés de taille 2x2 et ceux de taille 3x3, le ratio n'est pas de 4.
Pour compter le nombre de carrés de taille axa dans un carré de taille nxn, il faut (et il suffit de) compter le nombre d'emplacements possibles pour le sommet haut-gauche de notre carré axa.
Je n'ai pas dit que sa formule était fausse. De tout façon, mon niveau en mathématiques ne me le permettrait pas.
Cependant, ma formule ne donne pas le nombre de carrés de taille axa dans un carré de taille nxn, elle donne le nombre total de carrés (de taille 1 à x) dans un carré de taille x.
J'espère ne pas m'être mépris sur tes propos.
Edit : Je viens de la relire et de d'y réfléchir un peu plus. Je me suis en effet mépris. Toutes mes excuses.
Cependant, j'ai une humble question de débutant en maths. J'ai vu que le k se trouvait sous le sigma. Hors, selon Wikipédia, on incrémente le signe qui est en dessous. Dans cette formule, c'est le n qui est décrémenté.
La formule écrite par Ludobike dans son premier message est correcte.
Et dans son 4ème message, il y a du bon et du mauvais. L'avant dernière ligne est correcte, après des explications fausses. Et la dernière ligne est fausse.
Si l'on commence avec un carré de 1x1, on a 1 carré de 1x1.
Pour construire un carré de 2x2, on colle 3 carrés de 1x1 pour faire une forme de L et on y imbrique le carré d'avant. Cela fais 1 carré de 2x2 et $3+1 = 4$ carrés de 1x1.
Pour le carré de 3x3 on fait la même opération mais avec 5 carrés de 1x1. On a donc un carré de 3x3, 3 nouveaux carré des 2x2, un dans le coin et 2 sur les côtés soit 4 en tout et bien sûr 9 carrés de 1x1.
Pour le carré de 4x4 on a un nouveau carré de 4x4, 3 nouveaux de 3x3 soit 4 en tout, 5 nouveaux de 2x2 soit 9 et 7 nouveaux carrés de 1x1 soit 16. […]
C'est juste (sauf pour la formule à la fin, c'est plutôt $\sum_{k=0}^{n}k^2$), mais c'est quand même compliqué. Et finalement on ne voit pas apparaître clairement le passage intéressant, à savoir comment tu dénombres le nombre de carrés qui apparaissent "en plus" quand tu incrémentes la taille de la grille. Bon après en combinatoire, quand on connaît la réponse, c'est facile de s'arranger avec la vérité, mais là il existe quand même une preuve plus directe (bon, à part si on est très formel, et dans ce cas c'est plus une manière de s'en convaincre très fortement).
Oublie détails de type récurrence, essaye de compter le nombre de petits carrés de taille $k$ dans un gros carré de taille $n$. Bon, et vu que c'était ce qu'on t'avait déjà conseillé de faire, je propose en plus, si tu vois pas "tout de suite" comment montrer le résultat, de simplifier une "dimension" du problème, par exemple en ne comptant que les petits carrés dont le bord haut coïncide avec le bord haut du gros carré.
C'est un peu une méthode générale quand on a des problèmes en dimension > 1 : on se ramène à des dimensions plus petites en "projetant". Comme le problème est fortement symétrique, c'est ensuite facile à généraliser. Et puis ça peut aussi te permettre de voir comment est-ce qu'on passe d'une dimension à l'autre (et il faut s'en servir, parce que le saut de dimension n'est intuitivement géométrique que quand on passe de la dimension 1 à 2 et éventuellement — si on a une bonne vision dans l'espace — de la dimension 2 à 3).
Après une analyse statistique à deux variables, il apparait que ça ressemble énormément à une fonction polynôme de degré 4. Étonnamment, le nombre $1/3$ y occupe une place prépondérante.
Hmmm ta formule me renvoie environ 317 pour n = 5, je sais pas ce que c'est une "analyse statistique à deux variables", mais elle a pas l'air d'avoir trop marché ici.
Ceci dit je sais pas si ça a vraiment un sens de dire que 1/3 est prépondérant ici, à moins qu'on considère que 4 c'est 12/3, 8.5 c'est 19*3/2*1/3, etc. D'ailleurs (spoil) le nombre total de carrés devrait être exactement un certain polynôme de degré 3, et on pourrait éventuellement dire que le nombre 1/6 apparaît "magiquement", mais je pense pas que ça soit à classifier dans les faits extraordinaires.
Cependant, j'ai une humble question de débutant en maths. J'ai vu que le k se trouvait sous le sigma. Hors, selon Wikipédia, on incrémente le signe qui est en dessous. Dans cette formule, c'est le n qui est décrémenté.
$\sum_{i=1}^{6}{i^2} = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2.$
Quelqu'un aurait-il une explication plus "pédagogique" que Wiki sur le sujet svp ? J'avoue avoir du mal à comprendre ce point.
Je suis pas sûr d'avoir compris à quoi tu fais référence. C'est bien l'indice "du bas" qu'on incrémente, et on ne peut pas "décrémenter" l'indice du haut parce que c'est quelque chose de fixé "en dehors de la somme" (on ne touche pas à n ici, alors que k a lui une portée interne à la somme). Si tu préfères la vision "incrémentation", à la fin de la boucle suivante, somme vaudra exactement $\sum_{k=0}^n a_k$ :
1
2
intsomme=0;for(intk=0;k<=n;k++)somme+=a[k];
Une autre vision "avec les points de suspension" :
Hmmm ta formule me renvoie environ 317 pour n = 5, je sais pas ce que c'est une "analyse statistique à deux variables", mais elle a pas l'air d'avoir trop marché ici.
Ceci dit je sais pas si ça a vraiment un sens de dire que 1/3 est prépondérant ici, à moins qu'on considère que 4 c'est 12/3, 8.5 c'est 193/21/3, etc. D'ailleurs (spoil) le nombre total de carrés devrait être exactement un certain polynôme de degré 3, et on pourrait éventuellement dire que le nombre 1/6 apparaît "magiquement", mais je pense pas que ça soit à classifier dans les faits extraordinaires.
Oui, j'admets que je ne suis pas trop fier de cette partie de mon message. J'ai dû foirer quelque chose en recopiant la formule. Pour le 1/3, en effet c'est un peu vide de sens. J'avais juste été surpris de le voir apparaître plusieurs fois.
En tout cas, je crois avoir compris, il faudra que je le relise à tête reposée. Merci beaucoup pour ton explication !
Oui je sais pas ce qui m'a pris à la fin. Par contre je vois pas l'utilité de commencer avec $k=0$ puisque $0^2=0$ et $x + 0 = 0$.
Oublie détails de type récurrence, essaye de compter le nombre de petits carrés de taille $k$ dans un gros carré de taille $n$. Bon, et vu que c'était ce qu'on t'avait déjà conseillé de faire, je propose en plus, si tu vois pas "tout de suite" comment montrer le résultat, de simplifier une "dimension" du problème, par exemple en ne comptant que les petits carrés dont le bord haut coïncide avec le bord haut du gros carré.
Oui je sais pas ce qui m'a pris à la fin. Par contre je vois pas l'utilité de commencer avec $k=0$ puisque $0^2=0$ et $x + 0 = 0$.
Effectivement c'est exactement la même chose que $\sum_{k=1}^n k^2$. Je préfère commencer à $k=0$ parce que c'est plus "symétrique", notamment quand on veut faire des changements de variables de la forme k <-> n-k. Par exemple, dans l'exemple plus haut, c'est plus simple de se dire $\sum_{k=0}^n (n-k)^2 = \sum_{k=0}^n k^2$ que $\sum_{k=0}^{n-1} (n-k)^2 = \sum_{k=1}^n k^2$. Mais bon, ça change pas grand chose.
Oui c'est bon, d'ailleurs c'est ce à quoi ton raisonnement par récurrence devait aussi mener (mais de manière probablement plus alambiquée). C'est intéressant de voir la méthode que tu as utilisée pour compter le nombre de petis carrés de taille $k$. Qu'est-ce qui t'as permis de te convaincre qu'on pouvait effectivement placer $(n-k+1)^2$ carrés de taille $k \times k$ dans un truc de taille $n \times n$ ?
Qu'est-ce qui t'as permis de te convaincre qu'on pouvait effectivement placer $(n-k+1)^2$ carrés de taille $k \times k$ dans un truc de taille $n \times n$ ?
C'est une bonne idee de s'en inspirer, mais ca serait encore mieux que tu trouves "le bon argument" (je pense que ca t'aidera pour la dimension superieure anyway). On peut essayer de formaliser un peu pour que ca soit plus simple. On va dire qu'on represente le probleme qu'on s'est donne par l'ensemble des coordonnees $(x, y)$ ou $x$ et $y$ sont deux entiers. Tu peux te demander (1) comment on pourrait representer des "carres" (les "petits" et le "grand") dans ce modele (en gros, de quelles coordonnees tu aurais besoin) et (2) comment caracteriser les "petits carres" qui verifient la propriete d'etre dans le grand carre de taille $c$.
Du coup si je veux le prouver pour toutes les dimensions (si ça marche mais je pense que oui) je fais de la même manière ?
D’abord désolé pour la réponse tardive, j’avais pas mal de chose à faire ces dernières semaines.
C’est une bonne idee de s’en inspirer, mais ca serait encore mieux que tu trouves "le bon argument" (je pense que ca t’aidera pour la dimension superieure anyway). On peut essayer de formaliser un peu pour que ca soit plus simple. On va dire qu’on represente le probleme qu’on s’est donne par l’ensemble des coordonnees $(x, y)$ ou $x$ et $y$ sont deux entiers. Tu peux te demander (1) comment on pourrait representer des "carres" (les "petits" et le "grand") dans ce modele (en gros, de quelles coordonnees tu aurais besoin) et (2) comment caracteriser les "petits carres" qui verifient la propriete d’etre dans le grand carre de taille $c$.
Pour représenter un carré, j’ai besoin de 4 points, supposons donc $A,B,C,D$ quatre points, tel que $\forall P \in \{A;B;C;D\}, (X_P,Y_P) \in \{x \in \mathbb{N} | x \le n\}$ où $n$ est la longueur de coté du grand carré.
Pour que $ABCD$ soit un carré il faut que $AB = BC = CD = DA$, dans ce problème on ne s’intéresse qu’aux carrés dont les droites formés à partir des côtés sont parallèles à un des 2 axes x y, les longueurs des côtés peuvent donc s’écrire comme une simple différence.
Ainsi s’il on considère $S,M$ deux sommets adjacents et $n$ la longueur de côté du grand carré on a :
De ce fait les carrés peuvent être représentés par le jeu de coordonnées
$$A(k;n) \\
B(k;m) \\
C(p;m) \\
D(p;n)$$
Maintenant, intéressons nous à deux longueurs $n,m \in \mathbb{N}$ en supposant $m \le n$. Pour savoir le nombre de fois que l’on peut reporter la longueur $m$ dans $n$ on peut compter le nombre de longueur 1 que l’on peut soustraire à $n$ avant qu’elle soit inférieur à $m$, on trouve alors $n - m$, il faut alors rajouter 1 pour avoir le nombre de longueur $m$ que l’on peut mettre dans $n$ avec des coordonnés entières positives. Si l’on veut connaître le nombre de carrés $m \times m$ que l’on peut mettre dans $n \times n$ il suffit de mettre la formule précédente au carré soit $(n - m + 1)^2 = (n-m)^2 + 1$
On retrouve donc la formule $\sum^{n}_{k = 0}{k^2}$ assez facilement à partir de là.
Quelle est ta conjecture ? Et d’ailleurs, quelle est la generalisation ? Compter le nombre de cubes dans un cube ou le nombre de carres dans un cube ?
Ta modelisation ne va pas tout a fait. Deja j’ai pas tout compris, je pense qu’il y a des trucs bizarres dans les notations ($S$ et $M$ qui deviennent $A$ et $B$, $n$ et $m$ qui sont utilises pour differentes choses). Ensuite les deux implications que tu as ecrites sont equivalentes (elles sont contraposees l’une de l’autre) et ne sont pas equivalentes a la proposition en footnote (il manque la reciproque). Enfin, le modele des petits carres que tu donnes n’est pas satisfaisant parce que ce n’est pas une caracterisation (si on se prend 4 points $A$, $B$, $C$ et $D$ avec les coordonnees que tu as definies, parfois on va tomber sur un truc qui n’est pas un carre — en fait, on va obtenir tous les rectangles a coordonnees dans ta grille).
La consequence, c’est que la demonstration qui suit n’est pas tres formelle et ne se rapporte pas a ce que tu as ecrit avant (meme si encore une fois elle convient "intuitivement", si on veut "prouver definitivement" cette hypothese, il faut etre un peu plus rigoureux).
Pour te donner une idee de ce que pourrait etre une "bonne" modelisation (meme si t’en es pas loin, il manque en gros juste une contrainte supplementaire), il faut pas oublier que notre but c’est de compter des choses. On va dire pour le moment qu’on a une boite noire qui sait "compter" le nombre d’elements des parties finies de $\mathbf{N}$ (p.ex., dans $\{0, \ldots, n\}$ il y a $n+1$ elements), le nombre d’elements dans une union disjointe d’ensemble de ce type (p.ex. dans $\{0,1\} \cup \{4, ... n\}$ il y a $2+n-3$ elements) et le nombre d’elements d’un produit cartesien d’un nombre quelconque d’ensembles de ce type (p.ex. avec 2 ensembles : dans $\{0, \ldots, n\} \times \{4, \ldots, n\}$ il y a $(n+1)(n-3)$ elements). Du coup l’ideal ca serait de modeliser l’ensemble des petits carres comme un ensemble de ce type (par exemple si tu dis "un carre est strictement equivalent a la donnee de deux entiers, respectivement entre $0$ et $n$ et entre $3$ et $n$", la boite noire te repond : ok, il y a donc $(n+1)(n-3)$ carres).
Y a pas unicite de la bonne reponse a ces questions, mais je pense que quasiment toutes les methodes se generalisent tres facilement a la dimension $d$.
Connectez-vous pour pouvoir poster un message.
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
D'ailleurs (spoil) le nombre total de carrés devrait être exactement un certain polynôme de degré 3, et on pourrait éventuellement dire que le nombre 1/6 apparaît "magiquement", mais je pense pas que ça soit à classifier dans les faits extraordinaires.