Empilement de carrés dans un carré
Aller à la navigation
Aller à la recherche
Modèle:Voir homonymes L'empilement de carrés dans un carré est un problème d'empilement bidimensionnel dont l'objectif est d'empiler des carrés unités (côté 1) identiques de nombre Modèle:Mvar dans le carré le plus petit possible de côté a. Si a est un entier, la réponse est a2.
La plus petite valeur de a qui permet d'empiler des carrés de Modèle:Mvar unités est connue lorsque Modèle:Mvar est un carré parfait (auquel cas il est Modèle:Math), ainsi que pour Modèle:Mvar = 2, 3, 5, 6, 7, 8, 10 , 14, 15, 24 et 35. Le tableau ci-dessous indique la valeur optimale de a pour Modèle:Math[1]Modèle:,[2].
| Nombre de carrés unités Modèle:Mvar | Longueur d'un côté du carré extérieur | Figure | Démonstration[3] |
|---|---|---|---|
| 1 | 1 | Immédiat | |
| 2 | 2 | Frits Göbel - 1979 | |
| 3 | 2 | Frits Göbel - 1979 | |
| 4 | 2 | Immédiat | |
| 5 | Modèle:Math | 
|
Frits Göbel - 1979 |
| 6 | 3 | Michael Kearney et Peter Shiu - 2002 | |
| 7 | 3 | 
|
Erich Friedman - 1999 |
| 8 | 3 | Erich Friedman - 1999 | |
| 9 | 3 | Immédiat | |
| 10 | Modèle:Math | 
|
Walter Stromquist -1979 |
D'autres résultats qui ne permettent pas d'établir des empilements optimaux exacts sont connus. Par exemple :
- S'il est possible d'emballer n2 − 2 carrés unitaires dans un carré du côté a, alors a ≥ n[4].
- L'approche naïve dans laquelle tous les carrés sont parallèles aux axes de coordonnées et sont placés en contact bord à bord laisse un espace perdu de moins de a + 1 dans un carré du côté a[1].
- L'espace gaspillé d'une solution optimale est asymptotiquement o(a7/11) ((ici écrit en petite notation))[5].
- Toutes les solutions doivent gaspiller de l'espace au moins Ω(a1/2) pour certaines valeurs de a[6]
- 11 carrés unitaires ne peuvent pas être emballé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[2].