Téglahalom probléma

A téglarakás probléma , más néven blokk -rakás probléma , A líra ferde tornya, a könyvhalmozási probléma stb . , egy statikai probléma, amely abból áll, hogy téglalap alakú tömböket egymásra raknak egy olyan toronyba, amennyire csak lehetséges.

Megfogalmazás

A probléma így van megfogalmazva:

Helyezzen egymásra az azonos tömör négyszögletes paralelepipedonokat , és állítson össze egy stabil tornyot az asztal szélére úgy, hogy a széle feletti kiemelkedés maximális legyen. $N$

Történelem

A téglarakás probléma hosszú múltra tekint vissza a mechanikában és a matematikában egyaránt. Mike Paterson és szerzőtársai cikkeikben [1] egy hosszú hivatkozási listát közölnek erről a problémáról , amelyet a mechanikai munkák a XIX. század közepére nyúlnak vissza .

Döntések

Csak egy blokkal szintenként

Ideális esetben, ha minden szinten csak egy tökéletesen téglalap alakú blokk van, a túlnyúlás megegyezik a blokk szélességével [2] . Ez az összeg fele a harmonikus sorozat részösszegének . Mivel a harmonikus sorozatok divergálnak , a maximális túlnyúlás a végtelenbe hajlik , azaz . tetszőlegesen nagy túlnyúlást elérhet elegendő számú tömbbel. Minden egyes esetben a maximális túlnyúlás megközelítőleg egyenlő , azaz arányos a blokkok számának természetes logaritmusával . $\sum _{i=1}^{N}{\frac {1}{2i))$ $N$ ${\frac {1}{2}}\ln N$

N	Maximális túlnyúlás
N	töredék		decimális jelölés	relatív méret
egy	egy	/2	0.5	0.5
2	3	/négy	0,75	0,75
3	tizenegy	/12	~0,91667	0,91667
négy	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
nyolc	761	/560	~1,35893	1,35893
9	7 129	/5 040	~1,41448	1.41448
tíz	7 381	/5 040	~1,46448	1.46448

N	Maximális túlnyúlás
N	töredék		decimális jelölés	relatív méret
tizenegy	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
tizennégy	1 171 733	/720 720	~1,62578	1,62578
tizenöt	1 195 757	/720 720	~1,65911	1,65911
16	2436559	/1 441 440	~1,69036	1,69036
17	42 142 223	/24 504 480	~1,71978	1,71978
tizennyolc	14 274 301	/8 168 160	~1,74755	1,74755
19	275 295 799	/155 195 040	~1,77387	1,77387
húsz	55 835 135	/31 039 008	~1,79887	1,79887

N	Maximális túlnyúlás
N	töredék		decimális jelölés	relatív méret
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
harminc	9 304 682 830 147	/4 658 179 125 600	~1,99749	1,99749

Bármely szinten több blokkal

A szinten lévő további blokkok ellensúlyként használhatók, és több túlnyúlást adnak, mint az egy blokk a szinten. Még három blokk esetén is, ha két kiegyensúlyozott blokkot rakunk egy másik blokkra, akkor egy blokk túlnyúlását eredményezheti, míg egy egyszerű ideális esetben nem több . 2007-ben Mike Paterson és munkatársai kimutatták [1] , hogy a maximális túlnyúlás, amelyet egy szinten több blokkal lehet elérni, aszimptotikusan egyenlő , azaz arányos a blokkok számának kockagyökével, ellentétben azzal az egyszerű esettel, amikor a túlnyúlás arányos a blokkok számának logaritmusával. ${\frac {11}{12}}$ $c{\sqrt[{3}]{N}}$

Lásd még

Paterson férgei

Jegyzetek

↑ 12 Paterson et al, 2009 .
↑ Itt — blokkszám; a számozást felülről kezdjük. $én$

Linkek

Weisstein , Eric W. Könyvhalmozási probléma a Wolfram MathWorldnél .
Végtelen híd építése . PBS Infinite Series (2017. május 4.). Letöltve: 2018. szeptember 3. (határozatlan)
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler és Uri Zwick. Maximális túlnyúlás // American Mathematical Monthly. - 2009. - Vol. 116.—P. 763–787.