Русская Википедия:Упаковка квадратов в квадрате
Шаблон:Unsolved Упаковка квадратов в квадрате — одна из задач упаковки. Состоит в определении минимального размера квадратного контейнера (<math>a</math> — сторона контейнера) в который умещается <math>n</math> единичных квадратов (квадратов с размером стороны равной 1).
Впервые задача рассматривалась Эрдёшем и Грэмом в работе Шаблон:Sfn, до этого существовала как задача для венгерских студентов математиков в учебнике Эрдёша. В общем виде не решена Шаблон:Sfn.
Простейшим является случай, когда <math>n</math> есть квадрат целого числа (<math>n=1,4,9,16,...</math>), с решением — <math>a=\sqrt{n}</math> и незаполненным пространством, равным нулю.
Малое число квадратов
Шаблон:Кратное изображение Для малого числа единичных квадратов <math>n<100</math> оптимальные решения найдены для случаев <math>n = 1-10</math>, <math>14-16</math>, <math>23-25</math>, <math>34-36</math>, <math>46-49</math>, <math>62-64</math>, <math>79-81</math>, <math>98-100</math>.Шаблон:Sfn
Если <math>n</math> является полным квадратом, то наименьшее значение стороны квадратного контейнера <math>a=\sqrt{n}</math>. Для оптимальных решений при малых <math>n</math> , кроме случаев <math>n=5</math> и <math>n=10</math>, упаковка представляет собой единичные квадраты, расположенные параллельно сторонам контейнера с размером <math>a=\lceil\sqrt{n}\rceil</math>. Для <math>n=5</math> и <math>n=10</math> оптимальной является упаковка, использующая повёрнутые квадраты (см. рисунки справа)Шаблон:Sfn. Решение для <math>n=5</math> дано Гёбелем Шаблон:Sfn в 1979 году.
Оптимальность упаковки для <math>n=7, 8, 15 </math> впервые доказана Эль Мумни Шаблон:Sfn в 1999 году, для <math>n=6 </math> — Керни и Шиу Шаблон:Sfn в 2002 году, а в 2003 Стромквист Шаблон:Sfn доказал оптимальность решения для <math>n=10 </math>. В 2010 году Бентц Шаблон:Sfn находит оптимальное решение для <math>n=13 </math> и <math>n=46 </math>
Минимальным числом единичных квадратов, для которого на данный момент не найден оптимальный вариант упаковки, является <math>11</math>. Для этого случая наилучшая упаковка предложенна СтромквистомШаблон:Sfn. Она дает размер стороны контейнера <math>\textstyle a = 2+2\sqrt{4/5} \approx 3,789</math>.
Асимптотические результаты
В асимптотическом случае задача была сформулирована Эрдёшем и Грэмом в работе Шаблон:Sfn следующим образом. Необходимо определить какое максимальное количество единичных квадратов <math>n</math> может уместиться в большой квадратный контейнер со стороной размером <math>a \rightarrow \infty </math>. При решении этой задачи нужно минимизировать незанятое пространство, определенное в Шаблон:Sfn как
<math>W(a)= a^2 - sup\left\{|\mathcal P| \mid \mathcal P \right\} </math>,
где <math> \mathcal P </math> есть множество всех возможный упаковок единичных квадратов, а <math> | \mathcal P| </math> есть количество единичных квадратов. Отметим, что в случае целочисленного <math>a</math> получаем <math>n=a^2</math> и <math>W(a)=0</math>.
В случае не целочисленного значения <math>a</math> и «наивной» упаковки в виде рядов единичных квадратов, параллельных стенам контейнера, у незанятого пространства наблюдается линейный рост относительно <math>a</math> Шаблон:Sfn:
<math>W(a) \sim a(a-\lfloor a\rfloor)</math> .
Эрдёш и Грэм показали Шаблон:Sfn, что существует упаковка, дающая существенно нелинейную зависимость незанятого пространства от размера контейнера <math>W(a) \sim O(a^{7/11})</math> (запись в терминах «O» большое), и выдвинули гипотезу, что асимптотическое поведение оптимальной упаковки <math>W(a) \sim O(a^{1/2})</math> . Однако Рот и Воган в работе Шаблон:Sfn, для асимптотики из полуцелых значений <math>a</math>, получили <math>W(a) > c \sqrt{a}</math> , где <math>c</math> есть некая константа.
На данный момент наилучшей упаковкой в асимптотическом случае является упаковка, предложенная Грэмом и Чоном в работе Шаблон:Sfn с асимптотикой <math>W(a) \sim O(a^{3/5})</math>, а точная асимптотическая скорость роста незаполненного пространства остаётся открытой проблемой
См. также
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
