Упаковка квадратов в квадрате — одна из задач упаковки. Состоит в определении минимального размера квадратного контейнера ( — сторона контейнера) в который умещается единичных квадратов (квадратов с размером стороны равной 1).
Впервые задача рассматривалась Эрдёшем и Грэмом, до этого существовала как задача для венгерских студентов математиков в учебнике Эрдёша. В общем виде не решена.
Простейшим является случай, когда есть квадрат целого числа (), с решением и незаполненным пространством, равным нулю.
Малое число квадратов
Для малого числа единичных квадратов оптимальные решения найдены для случаев = 1—10, 14—16, 23—25, 34—36, 46—49, 62—64, 79—81, 98—100.
Если является полным квадратом, то наименьшее значение стороны квадратного контейнера . Для оптимальных решений при малых кроме случаев и упаковка представляет собой единичные квадраты, расположенные параллельно сторонам контейнера с размером . Для и оптимальной является упаковка, использующая повёрнутые квадраты (см. рисунки справа). Решение для дано Гёбелем в 1979 году.
Оптимальность упаковки для впервые доказана Эль Мумни в 1999 году, для — Керни и Шиу в 2002 году, а в 2003 году Стромквист доказал оптимальность решения для В 2010 году Бентц нашёл оптимальное решение для и
Минимальным числом единичных квадратов, для которого на данный момент не найден оптимальный вариант упаковки, является Для этого случая наилучшая упаковка предложенна Стромквистом. Она даёт размер стороны контейнера
Асимптотические результаты В асимптотическом случае задача была сформулирована Эрдёшем и Грэмом следующим образом. Необходимо определить какое максимальное количество единичных квадратов может уместиться в большой квадратный контейнер со стороной размером При решении этой задачи нужно минимизировать незанятое пространство, определённое как
где есть множество всех возможный упаковок единичных квадратов, а есть количество единичных квадратов. Отметим, что в случае целочисленного получаем и
В случае нецелочисленного значения и «наивной» упаковки в виде рядов единичных квадратов, параллельных стенам контейнера, у незанятого пространства наблюдается линейный рост относительно :
Эрдёш и Грэм показали, что существует упаковка, дающая существенно нелинейную зависимость незанятого пространства от размера контейнера (запись в терминах «O» большое), и выдвинули гипотезу, что асимптотическое поведение оптимальной упаковки Однако Рот и Воган для асимптотики из полуцелых значений получили где есть некая константа.
На данный момент наилучшей упаковкой в асимптотическом случае является упаковка, предложенная Грэмом и Чоном с асимптотикой а точная асимптотическая скорость роста незаполненного пространства остаётся открытой проблемой.
См. также
Квадрирование квадрата
Примечания
Литература
Категория:Задачи упаковки Категория:Открытые математические проблемы