Упаковка квадрата в квадрат - Square packing in a square

Упаковка квадратов в квадрат - это задача упаковки, цель которой состоит в том, чтобы определить, сколько квадратов со стороной один (единичных квадратов) можно упаковать в квадрат со стороной . Если - целое число, ответ будет , но точный или даже асимптотический объем потраченного впустую места для нецелого числа - открытый вопрос. ${\ displaystyle a}$${\ displaystyle a}$${\ displaystyle a ^ {2}}$${\ displaystyle a}$

Небольшое количество квадратов

5 единичных квадратов в квадрате со стороной ${\ displaystyle 2 + 1 / {\ sqrt {2}} \ приблизительно 2,707}$

10 единичных квадратов в квадрате со стороной ${\ displaystyle 3 + 1 / {\ sqrt {2}} \ приблизительно 3.707}$

Наименьшее значение , позволяющее упаковывать единичные квадраты, известно, когда это полный квадрат (в этом случае это так ), а также для 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47 и 48. Для большинства этих чисел (за исключением только 5 и 10) упаковка является естественной с квадратами, выровненными по оси, и составляет . На рисунке показаны оптимальные упаковки для 5 и 10 квадратов, двух наименьших чисел квадратов, для которых оптимальная упаковка включает наклонные квадраты. ${\ displaystyle a}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle {\ sqrt {n}}}$${\ displaystyle n = {}}$${\ displaystyle a}$${\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$

Самый маленький неразрешенный случай включает упаковку 11 квадратов в квадрат большего размера. 11 единиц квадрата не могут быть упакованы в квадрат со стороной меньше чем . Напротив, самая плотная упаковка из 11 квадратов находится внутри квадрата со стороной примерно 3,877084, немного улучшая аналогичную упаковку, обнаруженную ранее Уолтером Трампом . ${\ displaystyle \ textstyle 2 + 2 {\ sqrt {4/5}} \ приблизительно 3,789}$

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

Для больших значений длины стороны точное количество единичных квадратов, которые могут упаковать квадрат, остается неизвестным. Всегда можно упаковать сетку из выровненных по оси единичных квадратов, но это может привести к тому, что большая площадь останется непокрытой и потраченной впустую. Вместо этого Пол Эрдеш и Рональд Грэм показали, что для другой упаковки с помощью наклонных единичных квадратов потраченное впустую пространство может быть значительно сокращено до (здесь записано короткими обозначениями ). Позже Грэм и Фан Чанг еще больше сократили потраченное впустую пространство до . Однако, как доказали Клаус Рот и Боб Воган , все решения должны занимать как минимум пространство . В частности, когда это полуцелое число , потраченное впустую пространство как минимум пропорционально его квадратному корню. Точная асимптотическая скорость роста бесполезного пространства, даже для полуцелых длин сторон, остается открытой проблемой . ${\ displaystyle a}$${\ Displaystyle а \ раз а}$${\ displaystyle \ lfloor a \ rfloor \ times \ lfloor a \ rfloor}$${\ displaystyle 2a (a- \ lfloor a \ rfloor)}$${\ displaystyle o (а ^ {7/11})}$${\ displaystyle O (а ^ {3/5})}$${\ Displaystyle \ Omega {\ bigl (} а ^ {1/2} (а- \ lfloor a \ rfloor) {\ bigr)}}$${\ displaystyle a}$

Некоторое количество единичных квадратов никогда не бывает оптимальным количеством в упаковке. В частности, если размер квадрата допускает упаковку единичных квадратов, то должно быть так, что и упаковка единичных квадратов также возможна. ${\ Displaystyle а \ раз а}$${\ displaystyle n ^ {2} -2}$${\ Displaystyle а \ geq п}$${\ Displaystyle п ^ {2}}$

Квадратная упаковка по кругу

С этим связана проблема упаковки n единичных квадратов в круг с как можно меньшим радиусом. Для этой проблемы известны хорошие решения для n до 35. Вот минимальные решения для n до 12:

Смотрите также

• Упаковка круга в квадрат
• Возведение квадрата
• Прямоугольная упаковка

использованная литература

внешние ссылки

• Квадраты в квадратах , Центр упаковки Эриха, Эрих Фридман, Стетсонский университет