En mathématiques récréatives, le problème de l'empilement de carrés dans un carré est un problème d'empilement bidimensionnel dont l'objectif est de placer sans chevauchement carrés unités (côté de longueur 1) identiques dans le carré le plus petit possible de côté , ou, inversement d'empiler un maximum de carrés dans un carré donné. Sous cette dernière forme, le problème a reçu l'habillage suivant : combien de carrés de chocolat peut on ranger dans une boite carrée de dimension donnée ?
Lorsque est un carré parfait, un carré parfait moins 1, ou un carré parfait moins 2 : , il a été démontré en 2002 que le carré englobant le plus petit est celui de côté , et le rangement se fait simplement dans les cases, en laissant zéro, une ou deux cases vides. En dehors de ces cas, la plus petite valeur de qui permet d'empiler carrés unité n'est connue exactement que pour = 5 et = 6.
Exemples Le tableau ci-dessous indique la valeur optimale de pour ...
Nombre de carrés unités Longueur de côté a du carré englobantdensité Figure Démonstration 1 11 Immédiat 2 20,5 Frits Göbel - 1979 3 20,75 Frits Göbel - 1979 4 21Immédiat 5 0,682 Frits Göbel - 1979 6 30,667 Michael Kearney et Peter Shiu - 2002 7 3 0,778 Erich Friedman - 1999 8 30,889 Erich Friedman - 1999 9 31 Immédiat 10 0,728 Walter Stromquist -1979 Pour le cas , on sait que 11 carrés unitaires ne peuvent pas être empilés dans un carré de côté inférieur à . En revanche, l'empilement le plus serré connu de 11 carrés se trouve à l'intérieur d'un carré de longueur approximative de 3,8772.
On en déduit le tableau : +Côté du carré englobantNombre maximal de carrés unités inclus145910
Propriétés
On note la taille minimale du côté d'un carré pouvant contenir carrés unité sans chevauchement. Le nombre maximal de carrés unité que l'on peut placer sans chevauchement dans un carré de côté , est alors le nombre .
Cas général 1) La proposition suivante donne un encadrement de largeur inférieure à 1 pour la valeur de . Les carrés unitaires étant inclus sans chevauchement dans un carré de côté , l'aire du domaine qu'ils délimitent est inférieure ou égale à l'aire de ce carré, donc , d'où .
Soit maintenant ; par définition, ; on peut alors ranger carrés unitaires en utilisant les cases d'un carré de côté ; donc . On en déduit que .
2) Symétriquement, pour tout réel positif , on a l'encadrement : .
En effet, on peut ranger carrés unitaires dans un carré de côté inclus dans celui de côté , donc , et en raisonnant sur les aires on obtient .vignette|Cet échiquier mutilé illustre le fait qu'un carré de côté englobe carrés unitaires, mais ceci ne prouve pas que .
On en déduit que . Cas particuliers Plusieurs formules précises ont été établies pour des classes spécifiques de valeurs de :
1) Pour entier : vignette|Illustration de la formule 3 : empilement de 40 carrés (a=4, b=3) (avec les empilements triviaux vus plus haut).
Il est conjecturé qu'en fait , comme on le vérifie ci-dessus pour . 2) Pour entier : .
3) Pour entier et ou :
Remarque : La borne n'est pas toujours inférieure à la borne pour < 19.
Évaluation de la place perdue L'aire de la partie non recouverte par les carrés dans un rangement optimal est où ; l'encadrement vu ci-dessus, montre que , donc que .
Paul Erdős et Ronald Graham ont montré en 1975 que est même asymptotiquement et ont conjecturé que .. ; en 2020, l'exposant à été abaissé de 7/11 à 3/5 et il a été démontré qu'on ne peut l'abaisser en dessous de 1/2, mais cette conjecture reste non démontrée.
Références
Liens externes .
Carrés Catégorie:Carré Catégorie:Conjecture non résolue