Упаковка квадратов в квадрате

Нерешённые проблемы математики: Какова асимптотическая скорость роста незаполненного пространства при упаковке единичных квадратов в квадрат?

Упаковка квадратов в квадрате — одна из задач упаковки. Состоит в определении минимального размера квадратного контейнера (${\displaystyle a}$ — сторона контейнера) в который умещается ${\displaystyle n}$ единичных квадратов (квадратов с размером стороны равной 1).

Впервые задача рассматривалась Эрдёшем и Грэмом^[1], до этого существовала как задача для венгерских студентов математиков в учебнике Эрдёша. В общем виде не решена^[2].

Простейшим является случай, когда ${\displaystyle n}$ есть квадрат целого числа (${\displaystyle n=1,4,9,16,\dots }$), с решением ${\displaystyle a={\sqrt {n}}}$ и незаполненным пространством, равным нулю.

5 единичных квадратов в квадрате со стороной ${\displaystyle 2+1/{\sqrt {2}}\approx 2{,}707}$

10 единичных квадратов в квадрате с длиной стороны ${\displaystyle 3+1/{\sqrt {2}}\approx 3{,}707}$

Для малого числа единичных квадратов ${\displaystyle n<100}$ оптимальные решения найдены для случаев n = 1—10, 14—16, 23—25, 34—36, 46—49, 62—64, 79—81, 98—100^[2].

Если ${\displaystyle n}$ является полным квадратом, то наименьшее значение стороны квадратного контейнера ${\displaystyle a={\sqrt {n}}}$. Для оптимальных решений при малых ${\displaystyle n,}$ кроме случаев ${\displaystyle n=5}$ и ${\displaystyle n=10,}$ упаковка представляет собой единичные квадраты, расположенные параллельно сторонам контейнера с размером ${\displaystyle a=\lceil {\sqrt {n}}\rceil }$. Для ${\displaystyle n=5}$ и ${\displaystyle n=10}$ оптимальной является упаковка, использующая повёрнутые квадраты (см. рисунки справа)^[2]. Решение для ${\displaystyle n=5}$ дано Гёбелем в 1979 году^[3].

Оптимальность упаковки для ${\displaystyle n=7,8,15}$ впервые доказана Эль Мумни в 1999 году^[4], для ${\displaystyle n=6}$ — Керни и Шиу в 2002 году^[5], а в 2003 году Стромквист доказал^[6] оптимальность решения для ${\displaystyle n=10.}$ В 2010 году Бентц нашёл^[7] оптимальное решение для ${\displaystyle n=13}$ и ${\displaystyle n=46.}$

Минимальным числом единичных квадратов, для которого на данный момент не найден оптимальный вариант упаковки, является ${\displaystyle n=11.}$ Для этого случая наилучшая упаковка предложенна Стромквистом^[6]. Она даёт размер стороны контейнера ${\displaystyle a=2+2{\sqrt {4/5}}\approx 3{,}789.}$

В асимптотическом случае задача была сформулирована Эрдёшем и Грэмом следующим образом^[1]. Необходимо определить какое максимальное количество единичных квадратов ${\displaystyle n}$ может уместиться в большой квадратный контейнер со стороной размером ${\displaystyle a\to \infty .}$ При решении этой задачи нужно минимизировать незанятое пространство, определённое как

${\displaystyle W(a)=a^{2}-\sup\{|{\mathcal {P}}|\mid {\mathcal {P}}\},}$

где ${\displaystyle {\mathcal {P}}}$ есть множество всех возможный упаковок единичных квадратов, а ${\displaystyle |{\mathcal {P}}|}$ есть количество единичных квадратов. Отметим, что в случае целочисленного ${\displaystyle a}$ получаем ${\displaystyle n=a^{2}}$ и ${\displaystyle W(a)=0.}$

В случае нецелочисленного значения ${\displaystyle a}$ и «наивной» упаковки в виде рядов единичных квадратов, параллельных стенам контейнера, у незанятого пространства наблюдается линейный рост относительно ${\displaystyle a}$^[8]:

${\displaystyle W(a)\sim a(a-\lfloor a\rfloor ).}$

Эрдёш и Грэм показали^[1], что существует упаковка, дающая существенно нелинейную зависимость незанятого пространства от размера контейнера ${\displaystyle W(a)\sim O(a^{7/11})}$ (запись в терминах «O» большое), и выдвинули гипотезу, что асимптотическое поведение оптимальной упаковки ${\displaystyle W(a)\sim O(a^{1/2}).}$ Однако Рот и Воган для асимптотики из полуцелых значений ${\displaystyle a}$ получили ${\displaystyle W(a)>c{\sqrt {a}},}$ где ${\displaystyle c}$ есть некая константа^[9].

На данный момент^[] наилучшей упаковкой в асимптотическом случае является упаковка, предложенная Грэмом и Чоном^[8] с асимптотикой ${\displaystyle W(a)\sim O(a^{3/5}),}$ а точная асимптотическая скорость роста незаполненного пространства остаётся открытой проблемой.

• Упаковка окружностей в квадрат^[англ.]
• Квадрирование квадрата