Проблема с укладкой блоков

Первые девять блоков в решении проблемы укладки блоков одной ширины с указанными выступами

В статике , то проблема , блок-укладке (иногда известная как падающая башня Lire ( Johnson , 1955 ), также проблемы книжной укладки , или ряд других подобных терминов) представляет собой головоломка относительно укладки блоков на краю стол.

Заявление [ править ]

Проблема укладки блоков - это следующая загадка:

Разместите одинаковые жесткие прямоугольные блоки устойчивой стопкой на краю стола таким образом, чтобы свес был максимальным. ${\ displaystyle N}$

Патерсон и др. (2007) предоставляют длинный список ссылок по этой проблеме, восходящий к текстам по механике середины XIX века.

Варианты [ править ]

Одинарный [ править ]

Проблема единой ширины предполагает наличие только одного блока на любом заданном уровне. В идеальном случае идеально прямоугольных блоков решение проблемы одинарной ширины состоит в том, что максимальный вылет задается умноженным на ширину блока. Эта сумма составляет половину соответствующей частичной суммы гармонического ряда . Поскольку гармонический ряд расходится, максимальный вылет стремится к бесконечности по мере увеличения, что означает, что можно достичь любого произвольно большого вылета с достаточным количеством блоков. ${\ displaystyle \ sum _ {я = 1} ^ {N} {\ frac {1} {2i}}}$ ${\ displaystyle N}$

N	Максимальный вылет
N	выражается в виде дроби		десятичный	относительный размер
1	1	/ 2	0,5	0,5
2	3	/ 4	0,75	0,75
3	11	/ 12	~ 0,91667	0,91667
4	25	/ 24	~ 1,04167	1,04167
5	137	/ 120	~ 1,14167	1,14167
6	49	/ 40	1,225	1,225
7	363	/ 280	~ 1,29643	1,29643
8	761	/ 560	~ 1,35893	1,35893
9	7 129	/ 5 040	~ 1,41448	1,41448
10	7 381	/ 5 040	~ 1,46448	1,46448

N	Максимальный вылет
N	выражается в виде дроби		десятичный	относительный размер
11	83 711	/ 55 440	~ 1,50994	1,50994
12	86 021	/ 55 440	~ 1,55161	1,55161
13	1 145 993	/ 720 720	~ 1,59007	1,59007
14	1 171 733	/ 720 720	~ 1,62578	1,62578
15	1 195 757	/ 720 720	~ 1,65911	1,65911
16	2 436 559	/ 1 441 440	~ 1,69036	1,69036
17	42 142 223	/ 24 504 480	~ 1,71978	1,71978
18	14 274 301	/ 8 168 160	~ 1,74755	1,74755
19	275 295 799	/ 155 195 040	~ 1,77387	1,77387
20	55 835 135	/ 31 039 008	~ 1,79887	1,79887

N	Максимальный вылет
N	выражается в виде дроби		десятичный	относительный размер
21 год	18 858 053	/ 10 346 336	~ 1,82268	1,82268
22	19 093 197	/ 10 346 336	~ 1,84541	1,84541
23	444 316 699	/ 237 965 728	~ 1,86715	1,86715
24	1 347 822 955	/ 713 897 184	~ 1.88798	1,88798
25	34 052 522 467	/ 17 847 429 600	~ 1,90798	1,90798
26 год	34 395 742 267	/ 17 847 429 600	~ 1,92721	1,92721
27	312 536 252 003	/ 160 626 866 400	~ 1,94573	1,94573
28 год	315 404 588 903	/ 160 626 866 400	~ 1,96359	1,96359
29	9 227 046 511 387	/ 4 658 179 125 600	~ 1,98083	1,98083
30	9 304 682 830 147	/ 4 658 179 125 600	~ 1,99749	1,99749

Количество блоков, необходимых для достижения хотя бы длины блока за краем таблицы, составляет 4, 31, 227, 1674, 12367, 91380, ... (последовательность A014537 в OEIS ). ^[1] ${\ displaystyle N}$

Мульти-широкий [ править ]

Сравнение решений одинарной (вверху) и множественной (внизу) задачи укладки блоков с тремя блоками

Стеллажи с разной шириной, использующие уравновешивание, могут давать больший свес, чем штабели с одинарной шириной. Даже для трех блоков наложение двух уравновешенных блоков поверх другого блока может дать вылет 1, в то время как вылет в простом идеальном случае составляет не более 11/12. Как Патерсон и др. (2007) асимптотически показали, что максимальный вылет, который может быть достигнут с помощью многослойных штабелей, пропорционален кубическому корню из числа блоков, в отличие от случая одинарной ширины, в котором вылет пропорционален логарифму количество блоков.

Надежность [ править ]

Холл (2005) обсуждает эту проблему, показывает, что она устойчива к неидеализациям, таким как закругленные углы блоков и конечная точность размещения блоков, и вводит несколько вариантов, включая ненулевые силы трения между соседними блоками.

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

^ Слоан, Н. Дж. А. (ред.). «Последовательность A014537 (количество книг, необходимое для n длин книги с выступом в задаче сшивания книги по гармонике.)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.

Холл, JF (2005). «Развлечение с укладкой блоков». Американский журнал физики . 73 (12): 1107–1116. Bibcode : 2005AmJPh..73.1107H . DOI : 10.1119 / 1.2074007 .CS1 maint: ref = harv ( ссылка ).
Джонсон, Пол Б. (апрель 1955 г.). «Пизанская башня». Американский журнал физики . 23 (4): 240. Bibcode : 1955AmJPh..23..240J . DOI : 10.1119 / 1.1933957 .CS1 maint: ref = harv ( ссылка )
Патерсон, Майк ; Перес, Юваль ; Торуп, Миккель ; Винклер, Питер ; Цвик, Ури (2007). «Максимальный свес». arXiv : 0707.0093 [ math.HO ].CS1 maint: ref = harv ( ссылка )

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

Вайсштейн, Эрик В. "Задача укладки книг" . MathWorld .
«Строительство бесконечного моста» . Бесконечная серия PBS . 2017-05-04 . Проверено 3 сентября 2018 .

[1] Слоан, Н. Дж. А. (ред.). «Последовательность A014537 (количество книг, необходимое для n длин книги с выступом в задаче сшивания книги по гармонике.)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.

[1]