Nombre de carrés
Bonsoir
On veut découper un rectangle de dimensions 6x7 en carrés de côtés
entiers. Il en veut le moins possible. Quel est le plus petit nombre
de carrés qu’on peut obtenir dans ce découpage ?
La réponse est $42$ car 6 et 7 n'ont pas de diviseurs communs non ?
Ça me semble trop facile j'ai l'impression qu'il y a un piège.
Ça me semble trop facile j'ai l'impression qu'il y a un piège.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Tu n'as pas compris l'énoncé.
Ou alors, tu confonds le moins possible avec le plus possible.
Cordialement,
Rescassol
Avec un carré 6x6 il reste un rectangle 6x1 qu'on peut couper en 6 carrés, soit 7 carrés en tout.
Tu n'as pas le corrigé ?
Cordialement,
Rescassol
Dom.
Math Coss merci en effet j'avais mal compris la consigne encore une fois, j'ai supposé que les carrés devaient être identiques.
D'ailleurs seuls 5 élèves ont tenté l'exercice. Les réponses : 2, 3, 15, 4.
-- Schnoebelen, Philippe
Malheureusement pour OShine, 2012 est la seule année où il n'y a que les réponses et pas les corrigés.
Enfin… exhaustive… dès que l’effectif de ces carrés dépasse celui des solutions trouvées, c’est inutile de les considérer.
J'ai vu un exercice d'olympiade sur les pavages dans un carré 9 x 9 ça m'avait l'air extrêmement difficile. D'ailleurs, le corrigé disait que trouver la solution était accessible mais le démontrer était extrêmement difficile et n'avait été réussi par aucun candidats des olympiades.
L'exercice était de trouver le minimum de cases noires à colorier pour que dans chaque rectangle de taille 2 x 3 on ait au moins 2 carrés noirs qui se touchent.
* Un carré 6x6 . Pas de suspense, on doit compléter avec 6 petits carrés 1x1 --> n=7
* Un carré 5*5. On le place où on veut, de préférence dans un coin. Il nous reste une bande de largeur 1, dans laquelle on va mettre 5 carrés 1x1. On a déjà utilisé 6 carrés, et on on n'a toujours pas rempli notre rectangle.
* Un carré 4x4. On ne peut pas mettre de 2ème carré 4x4, ils se chevaucheraient. On va donc mettre des carrés 3x3
6x7-4x4, ça donne 26. Comment peut-on arriver à 26 avec une somme de carrés de nombres 1, 2 ou 3 ? on a 3x3+3x3+2x2 + 2x2 ... et on n'a pas mieux.
* pas de carré 4x4.
Les plus grands carrés utilisés sont donc des carrés 3x3, Avec 4 carrés 3x3, on arrive seulement à 36. Impossible de trouver une solution avec moins de 5 carrés.
On remplit ce qui reste, en mettant systématiquement un carré le plus grand possible, dans un coin du rectangle restant (par construction, la forme restante est toujours un rectangle).
Cet algorithme semble donner systématiquement le meilleur découpage.
Par ailleurs, il m'a expliqué que c'était impossible de faire avec moins de 5 carrés.
Je ne lui ai pas expliqué l'exercice, il a su comprendre la consigne seul ce qui est déjà très bien.
lol !
Quel critère ! Certes, un élève qui bafouille sur chaque mot, ce n'est pas rassurant, mais un élève qui a l'air convaincu, ça ne suffit pas.
Je te rappelle que tu es le prof, et lui est l'élève, et non l'inverse.
Plus généralement voir la suite A113881 de l'OEIS.
Il y a d'ailleurs une erreur sur cette dernière page puisque le troisième exemple donne T(6,7) = 6 alors que la bonne valeur est 5.
j'aimais bien ma petite méthode toute simple. Trop simple !
Pour un rectangle 12x11, on a effectivement 4 carrés de 3x3 alignés sur un bord du rectangle, puis 8x8 et 2 carrés 4x4.
Donc, nouvelle règle ... ou au moins une piste pour une nouvelle règle.
On a découpé le coté de longueur 12 en 4 segments de longueur 3. Seulement 4 carrés consommés. Il se trouve que 11-3=8, et pgcd(12,8) est un nombre relativement grand ...
Et donc, comme pgcd (12,8) est grand, le pavage du rectangle (12, 8) est économique.
Donc pour paver un rectangle (a,b), on chercher un $a_0$ diviseur de $a$, relativement grand, et tel que $pgcd( b-a_0, a)$ soit aussi relativement grand.
Et idem en inversant les rôles de $a$ et $b$.
Pour le rectangle (18,19) le minimum de carrés est égal à 7, on l'obtient avec un carré de côté 11, complété par un carré de côté 8, deux carrés de côté 7, un de 3 et deux de 5.
Pour le rectangle (104,105) le minimum de carrés est obtenu avec 10 carrés de tailles toutes différentes :
7, 12, 16, 19, 26, 28, 33, 44, 45, 60.
si on a une solution pour $(a,b)$ la solution doit être la même pour $(ka,kb)$, $k$ entier supérieur à 1.
Nous, la communauté mathématique, on aime bien les preuves puis les généralisations des énoncés.
Ca m'en bouche un coin (pour ne pas dire autre chose plus vulgaire).
Je n'espérais pas trouver une méthode qui marche à tous les coups, mais simplement une espèce de ligne directrice simple qui marche assez bien. ... Le fait de passer d'un rectangle 11x12 à un rectangle 8x12, et donc un rectangle 2x3 en fait, c'est une stratégie qu'on pouvait considérer comme efficace.
Mais là, des carrés de tailles toutes différentes, c'est quasiment la stratégie inverse.
Bon, pour le fun, j'ai quand même appliqué ma stratégie avec ce rectangle 104x105, et j'arrive à 13 carrés : (52, 52, 53, 17, 17, 17, 36, 15, 15, 6, 6, 3, 3) dans cet ordre.
Et ensuite, il y a un petit jeu qui est très amusant : connaissant la solution pour le rectangle 104x105, 10 carrés avec les 10 tailles données par Jandri, le but du jeu est de correctement placer les 10 carrés sur la figure.
A-t-on étudié la généralisation en dimension 3 avec un pavé et des cubes ?
Ça peut donner des casse-têtes rigolos.
Et au delà de la 3D ?
Cordialement,
Rescassol
-- Schnoebelen, Philippe
Mais une fois qu'on a la liste des 10 carrés, c'est assez facile de représenter la solution en commençant par le carré de 60, puis ceux de 44 et 45, puis 16, 28, 33, 26, 19, 12 et 7 :
Je pense que dans une classe de lycée, si on explique très clairement le contexte, si on montre 2 ou 3 grilles d'exemple pour être certain que tout le monde a compris la question, et si on donne une limite de 10 minutes, il y a la moitié des élèves qui n'y arrivent pas.
Après 9 mois de cours, l'équilibre est rétabli.