蜘蛛和苍蝇问题
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![](http://upload.wikimedia.org/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).