Empilement de carrés dans un carré
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
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
- ↑ a et b (en) Erich Friedman, Packing unit squares in squares: a survey and new results, (MR 1668055, lire en ligne).
- ↑ a et b (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).
Liens externes
- [vidéo] Mickaël Launay, Comment ranger des chocolats dans une boîte (mathématiquement) ? sur YouTube.
v · m Empilement | |
---|---|
Empilement de cercles | |
Empilement de sphères | |
Empilement de carrés |
|
Autres empilements |
|
Puzzles |
Portail de la géométrie