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

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

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

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

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

Малое число квадратов

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

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

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

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

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

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

Асимптотические результаты

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

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

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

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

$W(a)\sim a(a-\lfloor a\rfloor )$ .

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

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

См. также

• Упаковка окружностей в квадрат
• Квадрирование квадрата