Задача про стопку цегли
Задача про стопку цегли, завдання про стопці цегли, також відома як проблема укладання блоків (англ. Block-stacking problem), похила вежа лір (англ. The Leaning Tower of Lire), задача про складання книг і т.п. — задача статики, яка полягає в укладанні прямокутних блоків у вежу, як умога далі похилену в сторону.
Формулювання
Проблема формулюється наступним чином:
Поставити один на один однакових твердих прямокутних паралелепіпедів, зібравши стійку вежу на краю стола таким чином, щоб виступ за край був максимальний
Історія
Задача про стопку цегли має довгу історію як в механіці, так і в математиці. У своїх статтях Майк Патерсон і його співавтори надають[1] довгий список посилань на цю проблему, про яку йдеться в роботах з механіки, що відносяться до середини XIX століття.
Рішення
З тільки одним блоком на кожному рівні
В ідеальному випадку з тільки одним ідеально прямокутним блоком на кожному рівні звисання дорівнює ширини блоку[2]. Ця сума складає половину часткової суми гармонійного ряду. Оскільки гармонійний ряд розходиться, максимальне звисання прямує до нескінченності з ростом , тобто можна досягти будь-якого завгодно великого звису при достатній кількості блоків. У кожному конкретному випадку максимальне звис приблизно дорівнює , тобто пропорційний натуральному логарифму числа блоків.
N | Максимальний звис | |||
---|---|---|---|---|
Дріб | Десятинний
запис |
Відносний
розмір | ||
1 | 1 | /2 | 0.5 | |
2 | 3 | /4 | 0.75 | |
3 | 11 | /12 | ~0.91667 | |
4 | 25 | /24 | ~1.04167 | |
5 | 137 | /120 | ~1.14167 | |
6 | 49 | /40 | 1.225 | |
7 | 363 | /280 | ~1.29643 | |
8 | 761 | /560 | ~1.35893 | |
9 | 7 129 | /5 040 | ~1.41448 | |
10 | 7 381 | /5 040 | ~1.46448 |
N | Максимальний звис | |||
---|---|---|---|---|
Дріб | Десятинний
запис |
Відносний
розмір | ||
11 | 83 711 | /55 440 | ~1.50994 | |
12 | 86 021 | /55 440 | ~1.55161 | |
13 | 1 145 993 | /720 720 | ~1.59007 | |
14 | 1 171 733 | /720 720 | ~1.62578 | |
15 | 1 195 757 | /720 720 | ~1.65911 | |
16 | 2 436 559 | /1 441 440 | ~1.69036 | |
17 | 42 142 223 | /24 504 480 | ~1.71978 | |
18 | 14 274 301 | /8 168 160 | ~1.74755 | |
19 | 275 295 799 | /155 195 040 | ~1.77387 | |
20 | 55 835 135 | /31 039 008 | ~1.79887 |
N | Максимальний звис | |||
---|---|---|---|---|
Дріб | Десятинний
запис |
Відносний
розмір | ||
21 | 18 858 053 | /10 346 336 | ~1.82268 | |
22 | 19 093 197 | /10 346 336 | ~1.84541 | |
23 | 444 316 699 | /237 965 728 | ~1.86715 | |
24 | 1 347 822 955 | /713 897 184 | ~1.88798 | |
25 | 34 052 522 467 | /17 847 429 600 | ~1.90798 | |
26 | 34 395 742 267 | /17 847 429 600 | ~1.92721 | |
27 | 312 536 252 003 | /160 626 866 400 | ~1.94573 | |
28 | 315 404 588 903 | /160 626 866 400 | ~1.96359 | |
29 | 9 227 046 511 387 | /4 658 179 125 600 | ~1.98083 | |
30 | 9 304 682 830 147 | /4 658 179 125 600 | ~1.99749 |
З кількома блоками на будь-якому з рівнів
Додаткові блоки на рівні можуть використовуватися як противага і давати більше звисання, ніж варіант з одним блоком на рівні. Навіть для трьох блоків, укладання двох врівноважених блоків поверх іншого блоку, може дати звис в один блок, в той час як в простому ідеальному випадку — не більше . У 2007 році Майк Патерсон з співавторами показали, що максимальний звис, який може бути досягнутий за допомогою декількох блоків на рівні, асимптотично дорівнює , тобто пропорційний кубічному кореню з числа блоків, на відміну від простого випадку, коли звис пропорційний логарифму кількості блоків.
Див. також
Примітки
- Paterson et al, 2009.
- Здесь — номер блока; нумерация ведётся, начиная с верхнего.
Посилання
- 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.