Задача про стопку цегли

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

Формулювання

Проблема формулюється наступним чином:

Поставити один на один $N$ однакових твердих прямокутних паралелепіпедів, зібравши стійку вежу на краю стола таким чином, щоб виступ за край був максимальний

Історія

Задача про стопку цегли має довгу історію як в механіці, так і в математиці. У своїх статтях Майк Патерсон^[en] і його співавтори надають^[1] довгий список посилань на цю проблему, про яку йдеться в роботах з механіки, що відносяться до середини XIX століття.

Рішення

З тільки одним блоком на кожному рівні

В ідеальному випадку з тільки одним ідеально прямокутним блоком на кожному рівні звисання дорівнює $\sum _{i=1}^{N}{\frac {1}{2i}}$ ширини блоку^[2]. Ця сума складає половину часткової суми гармонійного ряду. Оскільки гармонійний ряд розходиться, максимальне звисання прямує до нескінченності з ростом $N$ , тобто можна досягти будь-якого завгодно великого звису при достатній кількості блоків. У кожному конкретному випадку максимальне звис приблизно дорівнює ${\frac {1}{2}}\ln 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

З кількома блоками на будь-якому з рівнів

Додаткові блоки на рівні можуть використовуватися як противага і давати більше звисання, ніж варіант з одним блоком на рівні. Навіть для трьох блоків, укладання двох врівноважених блоків поверх іншого блоку, може дати звис в один блок, в той час як в простому ідеальному випадку — не більше ${\frac {11}{12}}$ . У 2007 році Майк Патерсон з співавторами показали, що максимальний звис, який може бути досягнутий за допомогою декількох блоків на рівні, асимптотично дорівнює $c{\sqrt[{3}]{N}}$ , тобто пропорційний кубічному кореню з числа блоків, на відміну від простого випадку, коли звис пропорційний логарифму кількості блоків.

Див. також

Черв'яки Патерсона

Примітки

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

Посилання

Weisstein, Eric W. Book Stacking Problem(англ.) на сайті Wolfram MathWorld.
Building an Infinite Bridge. PBS Infinite Series. 4 травня 2017. Архів оригіналу за 10 лютого 2021. Процитовано 3 вересня 2018.
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick. Maximum Overhang. — American Mathematical Monthly. — 2009. — Vol. 116. — P. 763–787.

[FOOTNOTEPaterson_et_al2009-1] Paterson et al, 2009.

[2] Здесь $i$ — номер блока; нумерация ведётся, начиная с верхнего.

[1]

[2]