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

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

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

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

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

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

 

5 единичных квадратов в квадрате со стороной $2+1/\sqrt{2}\approx <!--\; \approx \; -->2.707$$2+1/{\sqrt {2}}\approx 2.707$ 

 

10 единичных квадратов в квадрате с длиной стороны $3+1/\sqrt{2}\approx <!--\; \approx \; -->3.707$$3+1/{\sqrt {2}}\approx 3.707$ 

Для малого числа единичных квадратов $n<100$  оптимальные решения найдены для случаев $n=1-<!--\; -\; -->10$$n=1-10$ , $14-<!--\; -\; -->16$$14-16$ , $23-<!--\; -\; -->25$$23-25$ , $34-<!--\; -\; -->36$$34-36$ , $46-<!--\; -\; -->49$$46-49$ , $62-<!--\; -\; -->64$$62-64$ , $79-<!--\; -\; -->81$$79-81$ , $98-<!--\; -\; -->100$$98-100$ .

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

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

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

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

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

$W(a)=a^2-<!--\; -\; -->sup\left\{|\mathcal{P}|\mid <!--\; \mid \; -->\mathcal{P}\right\}$$W(a)=a^{2}-sup\left\{|{\mathcal {P}}|\mid {\mathcal {P}}\right\}$ ,

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

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

$W(a)\sim <!--\; \sim \; -->a(a-<!--\; -\; -->\lfloor <!--\; \lfloor \; -->a\rfloor <!--\; \rfloor \; -->)$$W(a)\sim a(a-\lfloor a\rfloor )$  .

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

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

См. такжеПравить

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