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

Нерешенная проблема в математике:

Какова асимптотическая скорость роста потерянного пространства для квадратной упаковки в полуцелом квадрате?

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

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

5 единиц квадрата в квадрате со стороной

{ displaystyle 2 + 1 / { sqrt {2}} приблизительно 2,707}

10 единиц квадрата в квадрате со стороной

{ displaystyle 3 + 1 / { sqrt {2}} приблизительно 3.707}

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

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

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

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

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

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

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

Количество квадратов	Радиус круга
1	0.707...
2	1.118...
3	1.288...
4	1.414...
5	1.581...
6	1.688...
7	1.802...
8	1.978...
9	2.077...
10	2.121...
11	2.214...
12	2.236...

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

внешняя ссылка

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

[rpdg-1] а ^б Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), Проблемы исследования дискретной геометрии, Нью-Йорк: Springer, стр. 45, ISBN 978-0387-23815-9, МИСТЕР 2163782

[ks02-2] а ^б Кирни, Майкл Дж .; Шиу, Питер (2002), «Эффективная упаковка единичных квадратов в квадрат», Электронный журнал комбинаторики, 9 (1), Research Paper 14, 14 pp., МИСТЕР 1912796.

[3] Бенц, Вольфрам (2010), «Оптимальные упаковки 13 и 46 квадратов в квадрате», Электронный журнал комбинаторики, 17 (1), Исследовательская статья 126, МИСТЕР 2729375

[survey-4] а ^б Фридман, Эрих (2009), «Упаковка единичных квадратов в квадраты: обзор и новые результаты», Электронный журнал комбинаторики, Динамический обзор 7, МИСТЕР 1668055.

[5] Стромквист, Уолтер (2003), «Упаковка 10 или 11 квадратов в квадрат», Электронный журнал комбинаторики, 10, Исследовательский документ 8, МИСТЕР 2386538.

[6] Генсане, Тьерри; Ryckelynck, Philippe (2005), «Улучшенная плотная упаковка конгруэнтных квадратов в квадрате», Дискретная и вычислительная геометрия, 34 (1): 97–109, Дои:10.1007 / s00454-004-1129-z, МИСТЕР 2140885

[7] Эрдеш, П.; Грэм, Р. Л. (1975), «На упаковочные квадраты с равными квадратами» (PDF), Журнал комбинаторной теории, Серия А, 19: 119–123, Дои:10.1016/0097-3165(75)90099-0, МИСТЕР 0370368.

[8] *Чанг, Фань; Грэм, Рон, Эффективная упаковка единичных квадратов в большом квадрате (PDF), получено 2019-04-28

[9] Рот, К.Ф.; Воган, Р.С. (1978), «Неэффективность упаковки квадратов единичными квадратами», Журнал комбинаторной теории, Серия А, 24 (2): 170–186, Дои:10.1016/0097-3165(78)90005-5, МИСТЕР 0487806.

[10] Фридман, Эрих. «Квадраты в кругах».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]