スクエアパッキング

スクエアパッキングは、より大きな形状（通常は正方形または円）に、合同な正方形をいくつ詰め込めるか を決定することを目的とするパッキング問題です。

正方形への正方形詰めは、一辺の長さが のより大きな正方形の中に詰めることができる単位正方形（一辺の長さが の正方形）の最大数を決定する問題です。が整数の場合、答えは ですが、任意の非整数の場合の未充填空間の正確な量、さらには漸近量は未解決の問題です。^[1]${\displaystyle a}$${\displaystyle a}$${\displaystyle a^{2},}$${\displaystyle a}$

単位正方形のパッキングを可能にするの最小値は、 が完全な正方形のとき（この場合は）に知られています。また、2、3、5、6、7、8、10、13、14、15、24、34、35、46、47、48 についても知られています。これらの数のほとんど（5 と 10 のみ例外）では、パッキングは軸に沿った正方形による自然なパッキングであり、 です。ここでは天井（切り上げ）関数です。 ^{[2] [3]} この図は、5 と 10 の正方形の最適なパッキングを示しています。これらは、最適なパッキングが傾斜した正方形を含む最小の 2 つの正方形の数です。^{[4] [5]}${\displaystyle a}$${\displaystyle n}$${\displaystyle n}$${\displaystyle {\sqrt {n}}}$${\displaystyle n={}}$${\displaystyle a}$${\displaystyle \lceil {\sqrt {n}}\,\rceil }$${\displaystyle \lceil \,\ \rceil }$

未解決の最小のケースは である。11 個の単位正方形を 未満の辺の長さの正方形に詰め込むことはできないことが知られている。対照的に、11 個の正方形を最も密に詰め込んだ既知のケースは、ウォルター・トランプによって発見された辺の長さが約 3.877084 の正方形の内側である。^{[4] [6]}${\displaystyle n=11}$${\displaystyle \textstyle 2+2{\sqrt {4/5}}\approx 3.789}$

最もよく知られている3つの異なる角度の正方形の詰め合わせの最小の例は である。これは1998年にハワイ大学の学部生ジョン・ビッドウェルによって発見され、辺の長さは である。^[4]${\displaystyle n=17}$${\displaystyle a\approx 4.6756}$

以下はn =12までの値に対する最小解である: ^[7] (n=11の場合は未解決のまま)

辺の長さ の値がより大きい場合、正方形を詰め込むことができる単位正方形の正確な数は不明です。軸に沿った単位正方形のグリッドを詰め込むことは常に可能ですが、これにより、約 の大きな領域が覆われず無駄になる可能性があります。^[4] 代わりに、ポール・エルデシュとロナルド・グラハムは、傾斜した単位正方形による異なる詰め込みでは、無駄なスペースを まで大幅に削減できることを示しました(ここでは小さな o 表記で書かれています)。^[8] その後、グラハムとファン・チュンは、無駄なスペースを までさらに削減しました。^[9] しかし、クラウス・ロスとボブ・ヴォーンがを証明したように、すべてのソリューションは少なくとも のスペースを無駄にする必要があります。特に、が半整数の場合、無駄なスペースは少なくともその平方根に比例します。^[10]無駄なスペースの正確な漸近的増加率は、辺の長さが半整数であっても、未解決の問題のままです。^[1]${\displaystyle a}$${\displaystyle a\times a}$${\displaystyle \lfloor a\rfloor \!\times \!\lfloor a\rfloor }$${\displaystyle 2a(a-\lfloor a\rfloor )}$${\displaystyle o(a^{7/11})}$${\displaystyle O(a^{3/5})}$ ${\displaystyle \Omega {\bigl (}a^{1/2}(a-\lfloor a\rfloor ){\bigr )}}$${\displaystyle a}$

単位正方形の数によっては、詰め込みに最適な数にならない場合があります。特に、正方形の大きさが単位正方形の詰め込みを可能にする場合、 であり 、単位正方形の詰め込みも可能である必要があります。^[2]${\displaystyle a\times a}$${\displaystyle n^{2}-2}$${\displaystyle a\geq n}$${\displaystyle n^{2}}$

円内の正方形の詰め込みは、n個の単位正方形をできるだけ小さな半径の円内に詰め込むという関連問題です。この問題では、 n が35 までであれば良い解が知られています。以下はn =12までの最小の既知の解です: ^[11] (n=1 と n=2 の場合のみが最適であることが知られています)

• 正方形内の円の詰め込み
• 正方形を正方形にする
• 長方形パッキング
• ソファの移動問題

• フリードマン、エリック、「Squares in Squares」、Github、エリックのパッキングセンター