Empilement de carrés dans un carré

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 a².

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 $\sqrt 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 \leq 10$ ^[1]^,^[2].

Nombre de carrés unités $n$	Longueur d'un côté du carré extérieur	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/ \sqrt 2 \approx 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/ \sqrt 2 \approx 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 n² − 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(a^7/11) ((ici écrit en petite notation))^[5].
Toutes les solutions doivent gaspiller de l'espace au moins Ω(a^1/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 à $2+2{\sqrt {4/5}}\approx 3,789$ . 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

↑ ^{a et b} (en) Erich Friedman, Packing unit squares in squares: a survey and new results, 2009 (MR 1668055, lire en ligne).
↑ ^{a et b} (en) Walter Stromquist, Packing 10 or 11 unit squares in a square, vol. 10, 2003 (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, 2002 (MR 1912796, lire en ligne).
↑ (en) P. Erdős et R. L. Graham, On packing squares with equal squares, vol. 19, coll. « Series A », 1975, 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 », 1978, 170–186 p. (DOI 10.1016/0097-3165(78)90005-5, MR 0487806).

Liens externes modifier

[vidéo] Mickaël Launay, Comment ranger des chocolats dans une boîte (mathématiquement) ? sur YouTube.

Portail de la géométrie

[survey-1] {a et b} (en) Erich Friedman, Packing unit squares in squares: a survey and new results, 2009 (MR 1668055, lire en ligne).

[Stromquist-2] {a et b} (en) Walter Stromquist, Packing 10 or 11 unit squares in a square, vol. 10, 2003 (MR 2386538, lire en ligne).

[3] Comment ranger au mieux des carrés, des cercles et autres formes ? Jean-Paul Delahaye, 26 décembre 2018, Pour la science, N° 495

[4] (en) Michael J. Kearney et Peter Shiu, Efficient packing of unit squares in a square, vol. 9, 2002 (MR 1912796, lire en ligne).

[5] (en) P. Erdős et R. L. Graham, On packing squares with equal squares, vol. 19, coll. « Series A », 1975, 119–123 p. (DOI 10.1016/0097-3165(75)90099-0, MR 0370368, lire en ligne).

[6] (en) K. F. Roth et R. C. Vaughan, Inefficiency in packing squares with unit squares, vol. 24, coll. « Series A », 1978, 170–186 p. (DOI 10.1016/0097-3165(78)90005-5, MR 0487806).

[1]

[2]

[3]

[4]

[5]

[6]