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

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

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

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

Простейшим является случай, когда $n$ есть квадрат целого числа ($n=1,4,9,16,\dots$), с решением $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.$

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

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

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

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

где ${\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}),$ а точная асимптотическая скорость роста незаполненного пространства остаётся открытой проблемой.

См. также

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