Nombre de carrés — Les-mathematiques.net The most powerful custom community solution in the world

Nombre de carrés

Modifié (November 2021) dans Combinatoire et Graphes
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.
«1

Réponses

  • Bonjour,

    Tu n'as pas compris l'énoncé.
    Ou alors, tu confonds le moins possible avec le plus possible.

    Cordialement,
    Rescassol

  • Modifié (November 2021)
    Tu as ajouté une hypothèse selon laquelle les carrés sont identiques.
    Avec un carré 6x6 il reste un rectangle 6x1 qu'on peut couper en 6 carrés, soit 7 carrés en tout.
  • C'est une exercice de Polytechnique ?
  • Que dit le rapport du Jury ?
  • Bonjour,

    Tu n'as pas le corrigé ?

    Cordialement,
    Rescassol

  • DomDom
    Modifié (November 2021)
    Sans sarcasme, je trouve étrange de proposer une réponse arithmétique et de dire « c’est trop simple, il doit y avoir un piège ». 
    Si tu démontres que le problème revient à un problème de diviseurs et donc d’arithmétique élémentaire, ton doute sera levé et tu seras si tu te trompes ou pas. 
    Quant à savoir pourquoi j’interviens dans ce fil, je me le demande encore. 
    En fin de compte un petit sarcasme vespéral est toujours bon à prendre. 
    Cordialement
    Dom.
  • Modifié (November 2021)
    C'est un exercice de concours Kangourou dernière question pour départager les meilleurs (niveau 6ème 5ème) je n'ai pas de corrigé.
    Math Coss merci en effet j'avais mal compris la consigne encore une fois, j'ai supposé que les carrés devaient être identiques.
  • Attendons la réponse du fils de Bisam pour en savoir plus !
  • Modifié (November 2021)
    Je l'ai mis en question bonus en 5ème, un seul élève a trouvé la bonne réponse : 7.
    D'ailleurs seuls 5 élèves ont tenté l'exercice. Les réponses : 2, 3, 15, 4. 
  • Modifié (November 2021)
    Il est loin d'être évident que la meilleure solution soit 7 carrés puisque j'arrive à le faire en 5 carrés...
  • Oshine, il faut demander aux élèves de dessiner leur réponse.
    Par ailleurs, je m’étonne que le kangourou ne fournisse pas le corrigé.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • En effet, je pense même qu’on doit sanctionner la réponse « 2 » balancée comme ça, sans figure. 
  • Modifié (November 2021)
    Bisam a bien trouvé la bonne réponse (les réponses sont sur le site du Kangourou).

    Malheureusement pour OShine, 2012 est la seule année où il n'y a que les réponses et pas les corrigés.
  • Bien vu bisam je me demande comment un élève de 5ème peut démontrer que c'est 5.
  • DomDom
    Modifié (November 2021)
    Démontrer que c’est 5, c’est difficile. 
    Peut-être qu’une liste exhaustive des carrés dont la somme vaut l’aire du rectangle. 
    Pour commencer, disons…
    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. 
    Je dis bien « pour commencer » car après il faut paver le rectangle… ce qui a priori n’est peut-être pas possible. 
  • @OShine Dans les règles du concours, il n'est pas demandé de preuve.
  • On peut maintenant élargir la question à un rectangle mxn et chercher le nombre minimal de pièces dans un pavage par des carrés. 
  • DomDom
    Modifié (November 2021)
    Ça m’évoque un peu Fibonacci (ce n’est pas tout à fait ce pavage que l’on voit souvent) mais tellement vaguement que je n’ose m’y aventurer. 
    La méthode empirique avec mes sommes de carrés tombe à l’eau pour généraliser…
  • Modifié (November 2021)
    Un corrigé officiel du concours donne la solution 5 mais il n'y a pas d'explication, juste la réponse.
    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.
  • Essayons de placer des carrés le plus grand possible.
    * 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.
  • Lourrran pas mal comme raisonnement, merci.
  • Pour les rectangles de forme (n,n-1), un des 2 côtés est pair, on le découpe en 2 et on place 2 carrés identiques sur ce bord.
    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.
  • Modifié (November 2021)
    Un élève brillant de ma 5ème qui a 20/20 de moyenne en maths a trouvé la solution 5 et il a dessiné la figure donnée par Bisam.
    Par ailleurs, il m'a expliqué que c'était impossible de faire avec moins de 5 carrés. 
  • DomDom
    Modifié (November 2021)
    Hum… « brillant », personne n’a la même définition, puis « 20/20 » en maths n’a pas non plus la même signification selon les profs et les lieux, enfin « expliquer » ne me dit rien non plus car chacun jugera aussi si l’explication est valable.
    Mais au moins, c’est un élève qui sait se débrouiller et qui a compris la consigne. C’est déjà beaucoup. 
  • Modifié (November 2021)
    Oui mais il avait l'air convaincu de sa réponse.
    Je ne lui ai pas expliqué l'exercice, il a su comprendre la consigne seul ce qui est déjà très bien.
  • Oui, oui, sur l’aspect autonome que l’on perçoit, c’est déjà assez rare. 
    « Être convaincu » n’est pas un argument mathématique, par contre convaincre les autres l’est davantage (même si un bon vendeur sait vendre de la camelote).  
  • mais il avait l'air convaincu de sa réponse.

    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.
  • La méthode proposée par lourrran pour les rectangles de forme (n,n-1) ne donne pas toujours le plus petit nombre de carrés, par exemple quand $n=4$, $n=5$, $n=12$, $n=13$. Pour $n=12$ elle donne 8 carrés alors que le minimum est de 7 carrés (voir la suite A279317 de l'OEIS).
    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.
  • grrrrrr,
    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$.
  • Je ne pense pas qu'il existe de méthode générale.

    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.
  • Jandri t'as tracé un rectangle (104,105) ?  :o
  • On a une notion de rectangle primitif.
    si on a une solution pour $(a,b)$ la solution doit être la même pour $(ka,kb)$, $k$ entier supérieur à 1. 

    Zut ça a dû être dit plus haut…
  • La page OEIS pointée par Jandri mène à cet article de Richard Kenyon qui laisse peu d'espoir de trouver une solution générale ici.
  • Pas si simples ces exos pour collégiens ! 
  • Non mais il y a une différence de nature entre le cas $6\times7$ et le cas $p\times q$ !
  • Non. « L’avantage » est qu’ils n’exigent pas de preuve. 
    Nous, la communauté mathématique, on aime bien les preuves puis les généralisations des énoncés. 


  • 10 carrés de tailles toutes différentes ! 
    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.
  • Modifié (December 2021)
    Bonjour,

    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

  • Modifié (December 2021)
    Rescassol a dit :
    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.
    Tu me fais penser au casse-tête présent sur la table de l’APMEP au salon des jeux mathématiques fin mai où on démontre que $3^3+4^3+5^3=6^3$.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • L'exemple du rectangle (104,105) est donné sur la page  A279317 de l'OEIS, je ne l'ai pas trouvé tout seul !

    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 :


  • Oui, c'est assez facile, quand on a le cerveau correctement câblé.
    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.
  • Courrez vite chercher ce jeu : 

  • Donc l'élève de 6ème est meilleur que son prof ?  :'(
  • En début d'année, oui.
    Après 9 mois de cours, l'équilibre est rétabli.
  • Dom : tiens, c'est ce que j'offre à ma nièce à Noël ! J'ignorais complètement ce que c'était, me voilà rassuré !
  • Ce jeu est super...j'y ai joué avec mon petit fils, alors qu'il était en fin de CM1...il dégainait à toute allure 
     :) 
  • Modifié (December 2021)
    OShine a écrit 
    "Je l'ai mis en question bonus en 5ème, un seul élève a trouvé la bonne réponse : 7. D'ailleurs seuls 5 élèves ont tenté l'exercice. Les réponses : 2, 3, 15, 4. "
    Donc personne n'a répondu 5.
    Et un peu plus bas :
    "Un élève brillant de ma 5ème qui a 20/20 de moyenne en maths a trouvé la solution 5 et il a dessiné la figure donnée par Bisam".
    Quel mytho !
  • J’ai pensé qu’il avait deux 5e et qu’il n’avait pas encore regardé les copies de la deuxième. 

  • En effet dom, mais "ma cinquième" sous-entend souvent qu'on en a qu'une ? B)
    Et dans le même fil, la bonne réponse pour OShine est 42, au début du fil, puis 7 devient la bonne, puis 5 en 24h.  Et il a donné la question en bonus, en devoir en pensant que c'était 42, puis dit qu'un élève a donné la bonne réponse à savoir 7, et enfin que son cador a répondu 5 en lui faisant le schéma.
    Ça n'a ni queue ni tête.
  • Oui, on a l’impression que les mots sont envoyés comme si c’était au cours de la « réflexion », sans avoir été préparé du tout. 
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!