logo article ou rubrique
Avis de Recherche
Article mis en ligne le 20 juin 2016
dernière modification le 3 juillet 2017

par Alain Bougeard
logo imprimer

Solution de l’avis de recherche n°3

Rappel de l’avis de recherche n°3 :

Quel est le nombre minimum de carrés à côtés entiers nécessaires pour paver un rectangle de côtés $$$n$$$ et $$$m$$$ entiers ($$$n \lt m$$$) ?

Soit $$$K(n,m)$$$ ce nombre cherché.

Conjecture initiale $$$(R)$$$ : on peut se contenter de chercher les cas où $$$m$$$ et $$$n$$$ sont premiers entre eux car sinon $$$K(n,m) = K(n'd,m'd) = K(n',m')$$$ où $$$d = PGCD(n,m)$$$ et dans ce cas $$$n'$$$ et $$$m'$$$ sont premiers entre eux.

 

Recherche expérimentale

 

Visiblement ici $$$K(1,m) = m$$$


Donc les valeurs obtenues sont $$$({\color{red} 1}, 2, 3, 4, 5, 6 …)$$$

Si $$$m = 2k$$$ alors $$$K(2,m) = k$$$

Si $$$m = 2k+1$$$ alors $$$K(2,m) = k+2$$$


Donc les valeurs obtenues sont $$$({\color{red} 1,\color{red} 3}, 2, 4, 3, 5, 4, 6, …)$$$

Si $$$m = 3k$$$ alors $$$K(3,m) = k$$$

Si $$$m = 3k+1$$$ alors $$$K(3,m) = k+3$$$

Si $$$m = 3k+2$$$ alors$$$ K(3,m) = k+3$$$


Donc les valeurs obtenues sont $$$({\color{red} 1,\color{red} 4,\color{red} 4}, 2, 5, 5, 3, 6, 6, …)$$$

Si $$$m = 4k$$$ alors $$$K(4,m) = k$$$

Si $$$m = 4k+1$$$ alors $$$(4,m) = k+4$$$

Si $$$m = 4k+2$$$ alors$$$K(4,m) = k+2$$$

Si $$$m = 4k+3$$$ alors $$$K(4,m) = k+4$$$


Donc les valeurs obtenues sont $$$({\color{red} 1,\color{red} 5,\color{red} 3,\color{red} 5}, 2, 6, 4, 6, 3, 7, 5, 7 …)$$$

Il semblerait donc qu’il suffise de prendre le maximum de carrés de côté $$$n$$$ (i.e. en prendre $$$k = ent(m/n)$$$ ) et ensuite de trouver la solution pour $$$K(r,n)$$$ avec $$$r= m-kn$$$.

Malheureusement...

Si pour $$$m = 5k$$$ on obtient bien $$$K(5,m) = k$$$, pour $$$m = 5k+1$$$ les problèmes arrivent.

La méthode utilisée jusqu’à présent nous donne $$$K(5,m) = k+5$$$

Alors qu’en utilisant un carré de côté 5 de moins, le rectangle 5x6 peut être pavé par 5 carrés ce qui nous donne $$$K(5,m) = k-1+5 = k+4$$$

Donc à partir de maintenant nous allons changer de méthode en retirant $$$k-1$$$ grands carrés de côté $$$n$$$ (il semble impossible de faire mieux en retirant $$$k-2$$$ grands carrés mais je n’ai pas trouvé de démonstration satisfaisante : il s’agit donc d’une seconde conjecture $$$(R')$$$ qui devra être démontrée ou infirmée par un contre-exemple) et ensuite nous examinerons uniquement les rectangles $$$ n \times m$$$ avec $$$n \lt m \lt 2n$$$.

Pour ce faire nous utiliserons la méthode $$$H(i)$$$ consistant à utiliser le maximum de carrés de côté $$$i$$$ pour $$$i \in [1,n]$$$.

$$$H(n)$$$ étant ce que nous faisions jusqu’à présent (puisque nous essayons de placer un grand carré de cotén) et $$$H(1)$$$ fournissant la plus mauvaise solution $$$m \times n$$$.

Essayons avec $$$n = 5$$$ et $$$m = 6$$$

Donc nous avons $$$K(5,6) = 5$$$

Et nous pouvons en tirer quelques conclusions. Le meilleur résultat est obtenu pour $$$i \gt \dfrac{n}{2}$$$ et il semble qu’en dessous les résultats soient plus mauvais et notamment pour $$$i = 1$$$ ou $$$i = 2$$$ qui obtiennent de très mauvais scores. cela reste à confirmer.

D’autre part le bon résultat de 3 est dû au fait que ce soit un diviseur de $$$m$$$ et qu’en plus $$$n-3=2$$$ et que l’on puisse paver l’espace restant avec 3 carrés de côté 2. Sans pouvoir en tirer une règle il conviendra de faire plus attention au cas où $$$i$$$ est un "grand" diviseur de $$$n$$$ ou $$$m$$$.

Examinons les autres rectangles de largeur 5 :

Nous examinons tous les autres rectangles de largeur 5 et de longueur 7, 8 et 9.

À chaque fois c’est $$$H(5)$$$ qui donne la meilleure solution

Donc en résumé pour $$$K(5,m)$$$ nous obtenons :
$$$({\color{red}1,\color{red} 5,\color{red} 5,\color{red} 5,\color{red} 6}, 2, 6, 6, 6, 7, 3, 7, 7, 7, 8 ...)$$$

Explorons le cas $$$n = 6$$$

Ici 2 cas seulement à examiner car tous les autres sont donnés par des résultats déjà trouvés.

La méthode est toujours la même.

Par exemple pour 6x7

d’abord $$$H(6)$$$ qui donne $$$1+6=7$$$ puis $$$H(5)$$$ qui donne $$$1+3+5=9$$$

enfin $$$H(4)$$$ qui fournit la meilleure réponse car les suivants sont plus mauvais.

Donc pour $$$K(6,m)$$$ nous avons : $$$({\color{red}1,\color{red} 5,\color{red} 4,\color{red} 3,\color{red} 4,\color{red} 6}, 2, 6, 5, 4, 5, 7, 3 ,7, 6, 5, 6, 8 …)$$$

J’avais exploré beaucoup plus loin mais pas très loin quand même…

…quand un fidèle lecteur, Salvatore Tummarello, (qui cherchait de son côté et croyait avoir trouvé un algorithme fournissant le résultat mais qui ne fonctionnait pas pour 11×13), m’avertissait qu’il avait trouvé... sur internet (là où j’avais cherché désespérément mais en oubliant qu’on pouvait chercher aussi en anglais) un site étasunien qui s’intéressait à ce problème et qui semblait en avance sur nos recherches (pour rester modeste).

Notamment ils ont eu le mauvais goût de trouver un contre-exemple à ma conjecture selon laquelle il suffisait de chercher pour $$$n \lt m \lt 2n$$$ et d’ajouter autant de fois que nécessaire le nombre de carré de côté $$$n$$$. Évidemment il fallait aller chercher un peu plus loin puisqu’ils avaient montré que $$$K(112,53) = K(59,53)$$$ alors que $$$112=59+53$$$ ! Voici la preuve irréfutable :


Ils ont aussi mis au point une "machine" à fournir les résultats mais jusqu’à $$$n=350$$$ seulement pour l’instant ! (ce qui m’a permis de constater avec satisfaction que je trouvais, avec ma méthode artisanale, les mêmes résultats qu’eux... jusqu’à $$$n=10$$$).

Quant à savoir comment ils avaient fait et si leurs résultats étaient exacts je ne peux que vous inviter à aller le vérifier vous-mêmes en visitant leur site.

Si quelque spécialiste du C++ pouvait s’y plonger et nous expliquer…

Avis de Recherche n° 4

Les rondes de cercles :

Cet avis de recherche étant un peu long car détaillé, vous êtes invités à télécharger l’énoncé.



article suivant



retour au sommaire

Les chantiers de pédagogie mathématique n°169 juin 2016
La Régionale Île-de-France APMEP, 26 rue Duméril, 75013 PARIS



Téléchargements Fichier à télécharger :
  • Les rondes de cercles
  • 113.5 ko / PDF

Actus

Sommaire Chantiers septembre 2018

Édito La création de laboratoires de mathématiques, une des mesures (...)

Les Journées Nationales 2018

Bordeaux 2018

Les Journées Nationales de l’Apmep auront lieu cette année à (...)

Le concours 2018 - 2019

La Régionale Île-de-France de l’APMEP et l’IREM de Paris vous proposent (...)

Une nouvelle revue à l’APMEP en 2018 : « Au fil des maths »

Lors du comité national de mars 2016, il a été décidé de créer une nouvelle (...)

Brochure Jeux de l’Apmep

Une nouvelle brochure, en co-édition avec les Éditions du Kangourou, du (...)

Évènements à venir

0 | 5 | 10 | 15 | 20 | 25 | 30

04
juin
2018
horaire du lundi 4 juin 2018
au vendredi 21 décembre 2018

15
septembre
2018
horaire du samedi 15 septembre 2018
au vendredi 5 avril 2019

02
octobre
2018
horaire du mardi 2 octobre 2018
au dimanche 7 juillet 2019

17
octobre
2018
horaire du mercredi 17 octobre 2018
au samedi 20 octobre 2018

17
octobre
2018

Twitter APMEP IdF

pucePlan du site puceContact puceMentions légales puceEspace rédacteurs pucesquelette puce RSS

2013-2018 © APMEP Île-de-France - Tous droits réservés
Haut de page
Réalisé sous SPIP
Habillage ESCAL 4.1.19