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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

• Шаблон:Не переведено 5
• Квадрирование квадрата

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья