Blok istifleme sorunu - Block-stacking problem
İçinde statik, blok yığınlama sorunu (bazen olarak bilinir Eğik Lire Kulesi (Johnson 1955 ), Ayrıca kitap istifleme sorunuveya bir dizi başka benzer terim), bir tablonun kenarındaki blokların istiflenmesi ile ilgili bir bilmecedir.
Beyan
Blok istifleme sorunu aşağıdaki bilmecedir:
Yer özdeş katı dikdörtgen çıkıntıyı en üst düzeye çıkaracak şekilde bir masa kenarında sabit bir yığın halinde bloklar.
Paterson vd. (2007) bu soruna geri dönen uzun bir referans listesi sağlayın mekanik 19. yüzyılın ortalarından metinler.
Varyantlar
Tek geniş
Tek genişlikli sorun, herhangi bir düzeyde yalnızca bir bloğa sahip olmayı içerir. Mükemmel dikdörtgen blokların ideal durumunda, tek genişlikli sorunun çözümü, maksimum çıkıntının şu şekilde verilmesidir: bir bloğun genişliğinin katı. Bu toplam, karşılık gelen tutarın yarısıdır harmonik serinin kısmi toplamı. Harmonik seri farklılaştığından, maksimum çıkıntı eğilimi sonsuzluk gibi artışlar, yani yeterli blok ile herhangi bir keyfi olarak büyük çıkıntı elde etmenin mümkün olduğu anlamına gelir.
| N | Maksimum çıkıntı | |||
|---|---|---|---|---|
| kesir olarak ifade edilir | ondalık | göreceli boyut | ||
| 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 | Maksimum çıkıntı | |||
|---|---|---|---|---|
| kesir olarak ifade edilir | ondalık | göreceli boyut | ||
| 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 | Maksimum çıkıntı | |||
|---|---|---|---|---|
| kesir olarak ifade edilir | ondalık | göreceli boyut | ||
| 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 | |
En azından ulaşmak için gereken blok sayısı Tablonun kenarını geçen blok uzunlukları 4, 31, 227, 1674, 12367, 91380, ... (sıra A014537 içinde OEIS ).[1]
Çok geniş
Kullanarak çok geniş yığınlar dengeleme tek genişlikte bir yığından daha büyük çıkıntılar verebilir. Üç blok için bile, iki karşı dengeli bloğu başka bir bloğun üzerine istiflemek 1'lik bir çıkıntı verebilirken, basit ideal durumda çıkıntı en fazla 11/12'dir. Gibi Paterson vd. (2007) asimptotik olarak, çoklu genişlikte yığınlar ile elde edilebilecek maksimum çıkıntı, blok sayısının logaritması ile orantılı olan tek genişlikte durumun aksine, blok sayısının küp köküyle orantılıdır. .
Sağlamlık
Salon (2005) bu sorunu tartışır, bunun olduğunu gösterir güçlü yuvarlatılmış blok köşeleri ve sonlu blok yerleştirme hassasiyeti gibi ideal olmayanlara ve sıfırdan farklı olanlar da dahil olmak üzere çeşitli varyantlar sunar. sürtünme bitişik bloklar arasındaki kuvvetler.
Referanslar
- Hall, J.F. (2005). "Blok istifleme ile eğlence". Amerikan Fizik Dergisi. 73 (12): 1107–1116. Bibcode:2005AmJPh..73.1107H. doi:10.1119/1.2074007.CS1 bakimi: ref = harv (bağlantı).
- Johnson, Paul B. (Nisan 1955). "Eğik Lire Kulesi". Amerikan Fizik Dergisi. 23 (4): 240. Bibcode:1955AmJPh..23..240J. doi:10.1119/1.1933957.CS1 bakimi: ref = harv (bağlantı)
- Paterson, Mike; Peres, Yuval; Thorup, Mikkel; Winkler, Peter; Zwick, Uri (2007). "Maksimum çıkıntı". arXiv:0707.0093 [matematik.HO ].CS1 bakimi: ref = harv (bağlantı)
Dış bağlantılar
- Weisstein, Eric W. "Kitap İstifleme Sorunu". MathWorld.
- "Sonsuz Bir Köprü İnşa Etmek". PBS Infinite Serisi. 2017-05-04. Alındı 2018-09-03.