Главная
Упаковка квадратов в квадрате — одна из задач упаковки. Состоит в определении минимального размера квадратного контейнера ( a {displaystyle a} — сторона контейнера) в который умещается n {displaystyle n} единичных квадратов (квадратов с размером стороны равной 1).
Впервые задача рассматривалась Эрдёшем и Грэмом в работе , до этого существовала как задача для венгерских студентов математиков в учебнике Эрдёша. В общем виде не решена .
Простейшим является случай, когда n {displaystyle n} есть квадрат целого числа ( n = 1 , 4 , 9 , 16 , . . . {displaystyle n=1,4,9,16,...} ), с решением — a = n {displaystyle a={sqrt {n}}} и незаполненным пространством, равным нулю.
Малое число квадратов
Для малого числа единичных квадратов n < 100 {displaystyle n<100} оптимальные решения найдены для случаев n = 1 − 10 {displaystyle n=1-10} , 14 − 16 {displaystyle 14-16} , 23 − 25 {displaystyle 23-25} , 34 − 36 {displaystyle 34-36} , 46 − 49 {displaystyle 46-49} , 62 − 64 {displaystyle 62-64} , 79 − 81 {displaystyle 79-81} , 98 − 100 {displaystyle 98-100} .
Если n {displaystyle n} является полным квадратом, то наименьшее значение стороны квадратного контейнера a = n {displaystyle a={sqrt {n}}} . Для оптимальных решений при малых n {displaystyle n} , кроме случаев n = 5 {displaystyle n=5} и n = 10 {displaystyle n=10} , упаковка представляет собой единичные квадраты, расположенные параллельно сторонам контейнера с размером a = ⌈ n ⌉ {displaystyle a=lceil {sqrt {n}} ceil } . Для n = 5 {displaystyle n=5} и n = 10 {displaystyle n=10} оптимальной является упаковка, использующая повёрнутые квадраты (см. рисунки справа). Решение для n = 5 {displaystyle n=5} дано Гёбелем в 1979 году.
Оптимальность упаковки для n = 7 , 8 , 15 {displaystyle n=7,8,15} впервые доказана Эль Мумни в 1999 году, для n = 6 {displaystyle n=6} — Керни и Шиу в 2002 году, а в 2003 Стромквист доказал оптимальность решения для n = 10 {displaystyle n=10} . В 2010 году Бентц находит оптимальное решение для n = 13 {displaystyle n=13} и n = 46 {displaystyle n=46}
Минимальным числом единичных квадратов, для которого на данный момент не найден оптимальный вариант упаковки, является 11 {displaystyle 11} . Для этого случая наилучшая упаковка предложенна Стромквистом. Она дает размер стороны контейнера a = 2 + 2 4 / 5 ≈ 3 , 789 {displaystyle extstyle a=2+2{sqrt {4/5}}approx 3,789} .
Асимптотические результаты
В асимптотическом случае задача была сформулирована Эрдёшем и Грэмом в работе следующим образом. Необходимо определить какое максимальное количество единичных квадратов n {displaystyle n} может уместиться в большой квадратный контейнер со стороной размером a → ∞ {displaystyle a ightarrow infty } . При решении этой задачи нужно минимизировать незанятое пространство, определенное в как
W ( a ) = a 2 − s u p { | P | ∣ P } {displaystyle W(a)=a^{2}-supleft{|{mathcal {P}}|mid {mathcal {P}} ight}} ,
где P {displaystyle {mathcal {P}}} есть множество всех возможный упаковок единичных квадратов, а | P | {displaystyle |{mathcal {P}}|} есть количество единичных квадратов. Отметим, что в случае целочисленного a {displaystyle a} получаем n = a 2 {displaystyle n=a^{2}} и W ( a ) = 0 {displaystyle W(a)=0} .
В случае не целочисленного значения a {displaystyle a} и «наивной» упаковки в виде рядов единичных квадратов, параллельных стенам контейнера, у незанятого пространства наблюдается линейный рост относительно a {displaystyle a} :
W ( a ) ∼ a ( a − ⌊ a ⌋ ) {displaystyle W(a)sim a(a-lfloor a floor )} .
Эрдёш и Грэм показали , что существует упаковка, дающая существенно нелинейную зависимость незанятого пространства от размера контейнера W ( a ) ∼ O ( a 7 / 11 ) {displaystyle W(a)sim O(a^{7/11})} (запись в терминах «O» большое), и выдвинули гипотезу, что асимптотическое поведение оптимальной упаковки W ( a ) ∼ O ( a 1 / 2 ) {displaystyle W(a)sim O(a^{1/2})} . Однако Рот и Воган в работе , для асимптотики из полуцелых значений a {displaystyle a} , получили W ( a ) > c a {displaystyle W(a)>c{sqrt {a}}} , где c {displaystyle c} есть некая константа.
На данный момент наилучшей упаковкой в асимптотическом случае является упаковка, предложенная Грэмом и Чоном в работе с асимптотикой W ( a ) ∼ O ( a 3 / 5 ) {displaystyle W(a)sim O(a^{3/5})} , а точная асимптотическая скорость роста незаполненного пространства остаётся открытой проблемой