Empilement de cercles dans un carré

En mathématiques récréatives, le problème de l'empilement de cercles dans un carré consiste à déterminer le plus petit carré permettant d'empiler des cercles de même rayon de façon compacte au nombre de $n$ . De manière équivalente, l'objectif est de disposer $n$ points dans un carré de sorte que la plus petite distance entre eux soit la plus grande possible^[1]^,^[2].

Pour passer d'une formulations du problème à l'autre, notant $d_{n}$ le maximum de la plus petite distance entre deux points dans un carré de côté 1, le côté du carré minimal empilant des cercles de rayon égal à 1 est $L_{n}=2+{\frac {2}{d_{n}}}$ , ce qui donne $d_{n}={\frac {2}{L_{n}-2}}$ .

Démonstration

Partant d'une répartition de points dans un carré de côté 1 dont la distance minimale est égal à $d$ , on obtient, en entourant chaque point d'un cercle de rayon $d/2$ , un empilement de cercles dans un carré de côté $1+d$ ; en effectuant un homothétie de rapport $2/d$ , on obtient un empilement de cercles unité dans un carré de côté ${\frac {2}{d}}(1+d)=2+{\frac {2}{d}}$ .

Des solutions (démontrées optimales jusqu'à $n=30$ ) ont été calculées pour tout $n\leqslant$ 10 000^[3]. Les solutions pour $n$ allant de 1 à 20 sont indiquées ci-dessous^[3].

Lorsque $n$ est un carré parfait, l'empilement où les centres des cercles forment un réseau carré est optimal pour $n$ = 1, 4, 9, 16, 25 et 36 (les six premiers carrés non nuls), mais il cesse d'être optimal pour les carrés suivants, à partir de $n$ = 49^[3].

Les densités sont à comparer à la densité maximale d'un empilement de cercles de mêmes rayons, obtenue pour l’empilement hexagonal, égale à ${\frac {\pi }{2{\sqrt {3}}}}\approx 0{,}907$ .

Nombre de cercles ( $n$ )	Longueur du côté du carré ( $L_{n}$ )	$d_{n}$ ^[1]	Densité ( $n\pi /L_{n}^{2}$ )
1	2	∞	≈ 0,785
2	$2+{\sqrt {2}}$ ≈ 3,414...	${\sqrt {2}}$ ≈ 1,414	≈ 0,539
3	$2+{\frac {\sqrt {2}}{2}}+{\frac {\sqrt {6}}{2}}$ ≈ 3,931...	${\sqrt {6}}-{\sqrt {2}}$ ≈ 1,035	≈ 0,610
4	4	1	≈ 0,785
5	$2+2{\sqrt {2}}$ ≈ 4,828...	${\frac {1}{2}}{\sqrt {2}}$ ≈ 0,707	≈ 0,674
6	$2+{\frac {12}{\sqrt {13}}}$ ≈ 5,328...	${\frac {1}{6}}{\sqrt {13}}$ ≈ 0,601 A381485	≈ 0,664
7	$4+{\sqrt {3}}$ ≈ 5,732...	$4-2{\sqrt {3}}$ ≈ 0,536 A379338	≈ 0,669
8	$2+{\sqrt {2}}+{\sqrt {6}}$ ≈ 5,863...	${\frac {1}{2}}({\sqrt {6}}-{\sqrt {2}})$ ≈ 0,518 A101263	≈ 0,731
9	6	1/2 = 0,5	≈ 0,785
10	6,747...	≈ 0,421 A281065	≈ 0,690
11	7,022...	≈ 0,398	≈ 0,701
12	$2+15{\sqrt {\frac {2}{17}}}\approx 7,145$	${\sqrt {34}}/15\approx 0,389$	≈ 0,738
13	$(1+{\sqrt {3}})^{2}\approx 7,464$	$({\sqrt {3}}-1)/2\approx 0,366$	≈ 0,733
14	$6+{\sqrt {3}}$ ≈ 7,732...	$(8-2{\sqrt {3}})/13\approx 0,349$	≈ 0,736
15	$4+{\sqrt {2}}+{\sqrt {6}}$ ≈ 7,863...	$(2+2{\sqrt {2}}+{\sqrt {12}})/4\approx$ 0,341	≈ 0,762
16	8	1/3 ≈ 0,333	≈ 0,785
17	8,532...	≈ 0,306	≈ 0,734
18	$2+{\frac {24}{\sqrt {13}}}$ ≈ 8,656...	${\sqrt {13}}/12\approx$ 0,300	≈ 0,755
19	8,907...	≈ 0,290	≈ 0,752
20	${\frac {130}{17}}+{\frac {16}{17}}{\sqrt {2}}$ ≈ 8,978...	$(6-{\sqrt {2}})/16\approx$ 0,287	≈ 0,779

v · m Empilement
Empilement de cercles	Dans un cercle Dans un triangle équilatéral Dans un triangle isocèle rectangle Dans un carré Cercles d'Apollonius Théorème d'empilement de cercles Problème de Tammes (sur une sphère)
Empilement de sphères	Sphères d'Apollonius Dans une sphère Code parfait et code MDS
Empilement de carrés	Dans un carré Dans un cercle
Autres empilements	Problème de bin packing Empilement de tétraèdres Set
Puzzles	Bedlam Conway Diabolique Serpent Slothouber–Graatsma Soma

Empilement de cercles dans un carré

Références

Voir aussi

Related Articles