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

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

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

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) упаковка является естественной с квадратами, выровненными по оси, и составляет . ^{[2] [3]} На рисунке показаны оптимальные упаковки для 5 и 10 квадратов, двух наименьших чисел квадратов, для которых оптимальная упаковка включает наклонные квадраты. ^{[4] [5]}${\ displaystyle a}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle {\ sqrt {n}}}$${\ displaystyle n = {}}$${\ displaystyle a}$${\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$

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

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

Для больших значений длины стороны точное количество единичных квадратов, которые могут упаковать квадрат, остается неизвестным. Всегда можно упаковать сетку из выровненных по оси единичных квадратов, но это может привести к тому, что большая площадь останется непокрытой и потраченной впустую. ^[4] Вместо этого Пол Эрдеш и Рональд Грэм показали, что для другой упаковки с помощью наклонных единичных квадратов потраченное впустую пространство может быть значительно сокращено до (здесь записано короткими обозначениями ). ^[7] Позже Грэм и Фань Чанг сократили потраченное впустую пространство до . ^[8] Однако, как Клаус Рот и${\ 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})}$Боб Воан доказал, что все решения должны как минимум тратить впустую пространство . В частности, когда это полуцелое число , потраченное впустую пространство как минимум пропорционально его квадратному корню. ^[9] Точная асимптотическая скорость роста потерянного пространства, даже для полуцелых длин сторон, остается открытой проблемой . ^[1]${\ Displaystyle \ Omega {\ bigl (} а ^ {1/2} (а- \ lfloor a \ rfloor) {\ bigr)}}$${\ displaystyle a}$

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

Квадратная упаковка в круг [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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