Empilement de carrés dans un carré
Pour les articles homonymes, voir Empilement.
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 n 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 n unités est connue lorsque n est un carré parfait (auquel cas il est √n), ainsi que pour n = 2, 3, 5, 6, 7, 8, 10 , 14, 15, 24 et 35. Le tableau ci-dessous indique la valeur optimale de a pour n ≤ 10[1],[2].
| Nombre de carrés unités n | 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 | 2 + 1/√2 ≈ 2,707 | 
|
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 | 3 + 1/√2 ≈ 3,707 | 
|
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].
Références[modifier | modifier le code]
- (en) Erich Friedman, Packing unit squares in squares: a survey and new results, (MR 1668055, lire en ligne).
- (en) Walter Stromquist, Packing 10 or 11 unit squares in a square, vol. 10, (MR 2386538, lire en ligne).
- Comment ranger au mieux des carrés, des cercles et autres formes ? Jean-Paul Delahaye, 26 décembre 2018, Pour la science, N° 495
- (en) Michael J. Kearney et Peter Shiu, Efficient packing of unit squares in a square, vol. 9, (MR 1912796, lire en ligne).
- (en) P. Erdős et R. L. Graham, On packing squares with equal squares, vol. 19, coll. « Series A », , 119–123 p. (DOI 10.1016/0097-3165(75)90099-0, MR 0370368, lire en ligne).
- (en) K. F. Roth et R. C. Vaughan, Inefficiency in packing squares with unit squares, vol. 24, coll. « Series A », , 170–186 p. (DOI 10.1016/0097-3165(78)90005-5, MR 0487806).
