Задача о стопке кирпичей

Задача о стопке кирпичей, также известна как проблема укладки блоков (англ. Block-stacking problem), наклонная башня лир (англ. The Leaning Tower of Lire), задача о складывании книг и т. д. — задача статики, заключающаяся в укладке прямоугольных блоков в башню, как можно дальше выдающуюся в сторону.

Сдвиги девяти блоков «наклонной башни лир»

Формулировка

Проблема формулируется так:

Поставить друг на друга одинаковых твёрдых прямоугольных параллелепипедов, собрав устойчивую башню на краю стола таким образом, чтобы выступ за край был максимален.

История

Стопка монет: верхняя монета находится над областью, полностью находящейся вне самой низкой монеты

Задача о стопке кирпичей имеет долгую историю как в механике, так и в математике. В своих статьях Майк Патерсон (англ. Mike Paterson) и его соавторы приводят[1] длинный список ссылок на эту проблему, о которой говорится в работах по механике, относящихся к середине девятнадцатого века.

Решения

С только одним блоком на каждом уровне

В идеальном случае с только одним идеально прямоугольным блоком на каждом уровне свес равен ширины блока[2]. Эта сумма составляет половину частичной суммы гармонического ряда. Поскольку гармонический ряд расходится, максимальный свес стремится к бесконечности с ростом , т.е. можно достичь любого сколь угодно большого свеса при достаточном количестве блоков. В каждом конкретном случае максимальный свес приблизительно равен , т.е. пропорционален натуральному логарифму числа блоков.

NМаксимальный свес
дробьдесятичная
запись
относительный
размер
11/20,5 0.5
 
23/40,75 0.75
 
311/12~0,91667 0.91667
 
425/24~1,04167 1.04167
 
5137/120~1,14167 1.14167
 
649/401,225 1.225
 
7363/280~1,29643 1.29643
 
8761/560~1,35893 1.35893
 
97 129/5 040~1,41448 1.41448
 
107 381/5 040~1,46448 1.46448
 
NМаксимальный свес
дробьдесятичная
запись
относительный
размер
1183 711/55 440~1,50994 1.50994
 
1286 021/55 440~1,55161 1.55161
 
131 145 993/720 720~1,59007 1.59007
 
141 171 733/720 720~1,62578 1.62578
 
151 195 757/720 720~1,65911 1.65911
 
162 436 559/1 441 440~1,69036 1.69036
 
1742 142 223/24 504 480~1,71978 1.71978
 
1814 274 301/8 168 160~1,74755 1.74755
 
19275 295 799/155 195 040~1,77387 1.77387
 
2055 835 135/31 039 008~1,79887 1.79887
 
NМаксимальный свес
дробьдесятичная
запись
относительный
размер
2118 858 053/10 346 336~1,82268 1.82268
 
2219 093 197/10 346 336~1,84541 1.84541
 
23444 316 699/237 965 728~1,86715 1.86715
 
241 347 822 955/713 897 184~1,88798 1.88798
 
2534 052 522 467/17 847 429 600~1,90798 1.90798
 
2634 395 742 267/17 847 429 600~1,92721 1.92721
 
27312 536 252 003/160 626 866 400~1,94573 1.94573
 
28315 404 588 903/160 626 866 400~1,96359 1.96359
 
299 227 046 511 387/4 658 179 125 600~1,98083 1.98083
 
309 304 682 830 147/4 658 179 125 600~1,99749 1.99749
 

С несколькими блоками на любом из уровней

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

Дополнительные блоки на уровне могут использоваться как противовес и давать бо́льшие свесы, чем вариант с одним блоком на уровне. Даже для трех блоков укладка двух уравновешенных блоков поверх другого блока может дать свес в один блок, в то время как в простом идеальном случае — не более . В 2007 году Майк Патерсон с соавторами показали[1], что максимальный свес, который может быть достигнут с помощью нескольких блоков на уровне, асимптотически равен , то есть пропорционален кубическому корню из числа блоков, в отличие от простого случая, когда свес пропорционален логарифму количества блоков.

См. также

Примечания

  1. Paterson et al, 2009.
  2. Здесь — номер блока; нумерация ведётся, начиная с верхнего.

Ссылки

  • Weisstein, Eric W. Book Stacking Problem (англ.) на сайте Wolfram MathWorld.
  • Building an Infinite Bridge. PBS Infinite Series (4 мая 2017). Дата обращения: 3 сентября 2018.
  • Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick. Maximum Overhang // American Mathematical Monthly. — 2009. — Vol. 116. — P. 763–787.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.