Problém se stohováním bloků - Block-stacking problem

Prvních devět bloků v řešení problému se stohováním jednotlivých širokých bloků s vyznačenými převisy

v statika, problém se stohováním bloků (někdy známé jako Šikmá věž v Lire (Johnson 1955 ), také problém se stohováním knih, nebo řada dalších podobných výrazů) je hádanka týkající se skládání bloků na okraji stolu.

Prohlášení

Problém skládání bloků je následující hádanka:

Místo ${ displaystyle N}$ identické tuhý obdélníkový bloky ve stabilním zásobníku na okraji tabulky takovým způsobem, aby se maximalizoval přesah.

Paterson a kol. (2007) poskytnout dlouhý seznam odkazů na tento problém sahající až k mechanika texty z poloviny 19. století.

Varianty

Jeden široký

Jeden široký problém zahrnuje mít pouze jeden blok na dané úrovni. V ideálním případě dokonale obdélníkových bloků je řešením problému s jednou šířkou to, že maximální přesah je dán vztahem ${ displaystyle sum _ {i = 1} ^ {N} { frac {1} {2i}}}$ krát šířka bloku. Tato částka je polovinou odpovídající částečný součet harmonické řady. Protože harmonická řada se rozchází, maximální převis má sklony k nekonečno tak jako ${ displaystyle N}$ zvyšuje, což znamená, že je možné dosáhnout libovolně velkého převisu s dostatečným počtem bloků.

N	Maximální převis
N	vyjádřeno jako zlomek		desetinný	relativní velikost
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	Maximální převis
N	vyjádřeno jako zlomek		desetinný	relativní velikost
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	Maximální převis
N	vyjádřeno jako zlomek		desetinný	relativní velikost
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

Počet bloků potřebných k dosažení alespoň ${ displaystyle N}$ délky bloků za okrajem stolu jsou 4, 31, 227, 1674, 12367, 91380, ... (sekvence A014537 v OEIS ).^[1]

Multi-široký

Porovnání řešení problému se stohováním jednoho širokého (nahoře) a více širokého (dole) bloku se třemi bloky

Multi-wide stacks using vyvažování může poskytnout větší převisy než zásobník s jedinou šířkou. I u tří bloků může stohování dvou vyvažovaných bloků na jiný blok poskytnout přesah 1, zatímco přesah v jednoduchém ideálním případě je maximálně 11/12. Tak jako Paterson a kol. (2007) asymptoticky ukázal, že maximální převis, kterého lze dosáhnout pomocí multi-wide stacků, je úměrný kořenové krychli počtu bloků, na rozdíl od případu single-wide, ve kterém je převis úměrný logaritmu počtu bloků .

Robustnost

Hall (2005) pojednává o tomto problému, ukazuje, že je robustní k neidealizacím, jako jsou zaoblené rohy bloků a konečná přesnost umístění bloku, a zavádí několik variant včetně nenulového tření síly mezi sousedními bloky.

Reference

^ Sloane, N. J. A. (vyd.). "Pořadí A014537 (Počet knih požadovaných pro n přesahů délky knihy v problému se sešíváním harmonických knih.)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.

Hall, J. F. (2005). Msgstr "Zábava se skládáním bloků". American Journal of Physics. 73 (12): 1107–1116. Bibcode:2005AmJPh..73.1107H. doi:10.1119/1.2074007.CS1 maint: ref = harv (odkaz).
Johnson, Paul B. (duben 1955). "Šikmá věž v Lire". American Journal of Physics. 23 (4): 240. Bibcode:1955AmJPh..23..240J. doi:10.1119/1.1933957.CS1 maint: ref = harv (odkaz)
Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri (2007). "Maximální převis". arXiv:0707.0093 [matematika ].CS1 maint: ref = harv (odkaz)

externí odkazy

Weisstein, Eric W. „Problém se stohováním knih“. MathWorld.
„Stavba nekonečného mostu“. PBS Infinite Series. 2017-05-04. Citováno 2018-09-03.

[1] Sloane, N. J. A. (vyd.). "Pořadí A014537 (Počet knih požadovaných pro n přesahů délky knihy v problému se sešíváním harmonických knih.)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.

[1]