渡河問題

本文發表於 2010 年 02 月 17 日 09:31

jadem1.JPG台電登山社辦了武陵四秀登山活動,歸途中司機老爺出了一道「渡河謎題」,要舒展過筋骨的朋友也來動動腦,頓見人人爭相應戰,但都敗下陣來。筆者回家後將手上的謎題書找出來,發現其中三本有渡河謎題。

看完這些謎題之後,心中有兩個疑問,一是如何知道這是唯一最佳解?一是如何證明這謎題無解?苦思多日,很想把這兩個問題解決。幸賴小舅子幫忙找得一份資料,研讀後,得以寫出本文。

渡河謎題的解法約有三種,即試探法、圖解法和矩陣法;矩陣法頗近似於圖解法,有興趣的人可參閱參考資料。一般玩謎題或數學遊戲的人大概都採用試探法,本文將未成系統的方法均稱為試探法。有關試探法可參閱坡雅(G. Polya)著的「怎樣解題」(張憶壽教授譯,長橋出版社)。試探法的理論基礎不完全,往往賴個人的直覺和經驗,但它是解題的重要方法。本文主要介紹圖解法,它的優點是有一套理論,用以解釋為什麼那些路線不可能?為什麼那些路線最佳?

試探法(問題與解答)

在此先列舉一些渡河的謎題,有興趣的朋友可以先做,不要看解答。解答僅供參考,並不一定是最佳解。

【問題一】:一隊士兵來到河邊,橋斷河又深,正不知如何是好,忽見兩小孩汎舟,但舟太小,每次只能載兩小孩或一士兵,問如何渡河?

【問題二】:這個題目出現在十八世紀的文件中。

一農夫帶一隻狼、一隻羊及一個高麗菜渡河,而小舟一次只能載一人和狼(或羊或高麗菜)。假如農夫先帶高麗菜上船,則狼會吃掉羊;如果農夫先帶狼上船,則羊會吃掉高麗菜,只有農夫在場時,才不會發生上述情形,問如何渡河?

【問題三】:妒忌的丈夫

三對夫婦來到河邊渡河,但僅有一小舟,且舟小只能容納二人。由於丈夫妒忌心重,所以如果沒有丈夫在場,不管舟上或岸邊,沒有一婦人肯跟其他男人在一起,當然男女皆能操舟,問如何過河?

(一)如果是四對夫婦,小舟能容三人,則又如何?

(二)如果是四對夫婦,小舟只能容二人,但河中有一小島可供轉運,則又如何渡河?

(三)如果是五對夫婦,小舟能容三人,則又如何?

(四)如果是六對夫婦,小舟能容四人,則又如何?

【問題四】:土人及傳教士

三個傳教士與三個土人一起渡河,舟小一次僅能載二人,傳教士知道土人的習慣,如果土人比傳教士的人數多,則土人會吃掉傳教士,那麼如何安排才能安全渡河?又若其中僅一傳教士及一土人會操舟則又如何?

試探法解答

【解答一】:兩小孩先過河,其中一人返回原岸,一士兵渡河到對岸,另一小孩將舟划回原岸,然後重複上述步驟,即可將士兵全部載運到對岸。

【解答二】:農夫先將羊載運到對岸,然後返回原岸,再載運高麗菜到對岸,同時將羊載返原岸,將狼運往對岸,農夫空手返回原岸,將羊運往對岸,即完成渡河。

【解答三】:用A、B、C代表三個丈夫,妻子分別為a、b、c。首先,妻子b、 c二人過河,其中b返回原岸;然後b和a划往對岸,a操舟返回原岸;丈夫B、C渡河到對岸,夫婦B、b操舟返回原岸;A、B渡河到對岸,c操舟返回原岸;b、c渡河到對岸,b操舟返回原岸;a、b渡河到對岸,完成渡河。

讀者可用小物品模擬渡河程序,解決另外四個子題。

【解答四】:以M代表傳教士,C代表土人。首先兩土人C、C渡河對岸,C操舟返回原岸;C、C渡河到對岸,C操舟返回原岸;兩傳教士M、M渡河到對岸,C、M操舟返回原岸;M、M渡河到對岸,C操舟返回原岸;C、C渡河到對岸,C操舟返回原岸;C、C渡河到對岸,完成了渡河。

圖解法

用圖解法來解渡河謎題,如土人和傳教士或妒嫉的丈夫等問題,比較簡便。基本的想法是,在問題中,每一次船開到另一岸,岸邊人數就改變,我們不必在意那些人在那一岸邊,只在意各種狀態中人數的改變,而各種可能狀態之間的轉變,可以用圖形表示。

一、狀態圖

現在以問題四為例來討論圖解法,依史瓦茲(Schwartz)的作法,我們令

m=傳教士在原岸邊的人數

c=土人在原岸邊的人數

f1.JPG

有序對(c, m)表示任何時刻,船不在河中時的系統狀態,沒有必要說明對岸的狀態,因為兩岸的人數永遠保持各三人(假定不發生不幸事件),所以c與m之可能情況為0≦ m ≦3,0≦ c ≦3而且m、c皆為自然數,則總共有16種可能(見圖一)。但包含有一些不允許發生的情形,如m=1,c=3;又如m=2,c=1,單從數字看好像可以,其實對岸有一個傳教士兩個土人,亦為不允許發生之狀態。 事實上,允許的狀態(c,m)必須滿足下列限制﹕(a)0≦ c ≦3(b)0≦ m ≦3(c)c=m  或  m=0  或 m=3

將滿足上述條件的點(狀態)以圓圈圖示在圖一之直角坐標上,則有10種狀態滿足要求(圖上成Z字形者),我們稱這個圖形為系統狀態圖。

二、狀態間的轉換

狀態間的轉換,可用有向線或弧等幾何圖形連接,做出有向圖形,點或頂點代表各狀態,邊(連線)則代表渡河行為。那些頂點該連成邊呢?我們發現,船每次到對岸,c或m的數值減少2或1;而返原岸時,c或m的數值增加1或2。

f2.JPG

引用上述規則,我們將可能路徑連接(見圖二),由於船可以在兩岸來回,先不考慮題意,則圖形之每一邊可以向兩方向走,也就是從(3,3)可以到(1,3),從(1,3)可以到(3,3)(船返回原岸,而將乘客運回原岸,狀態沒有任何改變,這種情形要避免)。船小只能載二人,且返回原岸必須有人操舟,因此圖形上邊的方向是上下或左右交替變換。由原始狀態(3,3)開始,照上述規則,就能得到圖三(A)之解答,圖中虛線表示船返回原岸,實線表示駛向對岸。從圖二我們有一直覺,似乎走對角線是最便捷的,但從(3,3)到(2,2)到(1,1)到(0,0)不是一可能的能答,因為我們需考慮只能載二人及要有人操舟返回的限制(即路徑的上下、左右交替變換)。

f3a.JPG

三、存在、唯一、最小化

很自然的,對圖三(A)的解答馬上會產生以下的問題:這個解答是不是唯一的?若傳教士和土人的人數增加,是否有解?如果一個問題有許多解答,是否有最少的渡河次數?

圖解法有助於解答這些問題。讓我們將允許的狀態分為下列三種:

一、狀態T表示頂部(m=3)各狀態

二、狀態B表示底線(m=0)各狀態

三、狀態D表示對角線(0<m=c<3)各狀態

在船僅能容納二人的條件下,不可能從狀態T直接到達狀態B,因此任何解答的路線必須包括狀態D。此外,假如我們從(2,3)或(3,3)到(2,2),但次一步驟卻只有又回到(2,3)或(3,3)的路徑好走,結果沒有達成任何事情,而產生了無效的環路,您可以在這環路上來回幾趟,但達不到渡河的目的。因此,當路線離開狀態T,就必須走到(1,1),且唯一的方法是從(1,3)開始;到達狀態B的唯一方法是走到(2,2)和(2,0)。所以,解答的路線必須包括下列的次序:

→(1,3)→(1,1)→(2,2)→(2,0)→………

f3b.JPG

而(1,3)能由(3,3)達到(所謂達到是船在原岸),即

(3,3)→(1,3)→(2,3)→(0,3)→(1,3),

或(3,3)→(2,2)→(2,3)→(0,3)→(1,3)。

f3c.JPG

從(2,0)到(0,0)的路線有二條,因此問題四的圖解法共有四個〔見圖三(A)、(B)、(C)、(D)〕,其路徑是實線之後必接虛線,構成一有向圖形(direct ed graph or diagram)。

f3d.JPG

同理可解一般化的問題。舉例來說,四個土人和四個傳教士,在小舟僅能容二人的條件下,是無法安全渡河的。由狀態圖(見圖四)即可予以證明,離開狀態T而沒有馬上回到原處的情形,其中之一是必須從(2,4)到(2,2),而次一步是到(3,3)或回到(2,4),從(3,3)是沒有路徑到達狀態B,也不能到(1,1),所以本題無解。

f41.JPG

假如小舟能容納三人,而其他條件不變的話,很容易發現五個土人和五個傳教士可安全渡河;但六個傳教士和六個土人就不行。假如小舟能容納四人,則任何人數的傳教士和土人都能安全渡河,因為如此就可沿對角線而到達狀態B。如圖五,是六個傳教士六個土人,而小舟能容納四人的情形。對角線解並不一定是最少的渡河次數,舉例來說,六個傳教士及六個土人,小舟能容納五人,則圖五在對角線上的解,需九次才完成渡河,但圖六的解卻只要七次即可完成渡河。無論如何,若小舟容納偶數乘客,4≦ B ≦ M   M是傳教士或土人人數),則沒有可達(0,0)而渡河次數少於沿對角線路徑者。我們首先注意到,路徑必須經歷一對角線狀態以及離開狀態T的最好方式,第一步是送B個土人到對岸,舟返回時帶一個土人,然後送B-1個傳教士〔見圖七(a)〕,如此三個步驟就運送B-1個傳教士及B-1個土人;另一方面,同樣結果可以由沿對角線而達成〔見圖七(b)〕。

f5.JPG

f6.JPG

f7.JPG

四、一般化的謎題

應用圖解法可使一些基本謎題的變形較容易分析。舉例來說,不僅可以限定小舟的最大容量,也可以限定最小容量(但需大於1)。事實上,任何限制條件都可以引入,因此狀態圖中可能狀態的改變,諸如渡河數、最後狀態、狀態所經過順序之函數,在這複雜的情況中,可能就需要借助計算機了。

假如問題型式、人員或限制條件增多,謎題會變得更複雜。例如用史瓦茲的方法來討論下列問題,M個傳教士能划船,R個土人能划船,而C個土人不能划船,則系統狀態可用三元組(c, r , m)表示。在平面上可將同一m值繪在同一平行線上,如圖八所示,係m=3, r=1, c=2 之解答,其路徑為(2,1,3)→(1,0,3)→(1,1,3)→(0,0,3)→(0,1,3)→(0,1,1)→(1,1,2)→(1,0,1)→(2,0,2)→(2,0,0)→(2,1,0)→(1,0,0)→(1,1,0)→(0,0,0)。

f8.JPG

若問題再擴充更一般化,也許要根據史瓦茲的分析法或貝爾門的動態規畫法,賴電子計算機之助才行。

五、妒忌的丈夫謎題

我們用前面所述的方法來討論問題三,以結束本文。這謎題相當古老,原來出處已不可考,曾因義大利數學家塔塔格利亞(Tartaglia, 1510~1557 年)的錯誤解答而出名。

首先,我們定義狀態的有序對為(w,h),h是原岸的丈夫數,w是原岸的妻子數。初看之下,這樣的定義不能滿足題意的要求,因為不同的情況可能會放在相同的狀態。舉例來說,假如我們以A、B、C表示三個丈夫,而其對應的妻子以a、b、c表示,則在原岸之情況若是A和a或A和b或A和c,其狀態數皆為h=w=1,雖然後面兩種狀態是不允許的,但都歸類為狀態(1,1)。因此,我們需定狀態圖中的僅表示允許的狀態,上述的困難就不成為障礙了。狀態(1,1)僅表示A與a,或B與b或C與c在原岸的情形,我們沒有必要分辨他們之間的不同。

現在,系統的狀態已定義好,我們可以繪出如圖一的系統狀態圖,只不過要把坐標c、m改為w、h。必須注意的是,對角線上的狀態只允許夫妻配對的情況(即Aa、Bb、Cc),因此(2,2)表示 A、B、a、b或A、C、a、c、或B、C、b、c,而不是A、B、a、c。現在很清楚地表示出來,如圖三是土人和傳教士謎題的解答,也正是妒忌的丈夫謎題僅有的可能解答,而僅須核對(1,3)→(1,1)→(2,2)狀態轉移是否能合理達成。

結語

在圖形理論中,圖形的定義是由一個點集合和一個兩點間連線的集合而成,圖形中若加上箭號則成有向圖形,有向圖形在作業研究(operation research)中是很有價值的,它能解決生產線問題(排定工廠中各個製造程序的最佳先後秩序);在工程管理中的臨界路線法(critical path method),是縮短工期或解決運輸等問題的一種有向圖形之應用。

用有向圖形來解決渡河問題,是一種極佳的創見,問題四土人(或傳教士)的人數是n,而小舟能容納四人,則需2n-3次才可完成渡河。如果小舟能容納四人以上之偶數人數,則對角線解是最佳解。如果n比小舟所能容納偶數人數(四人以上,不含四人)多一,則最佳解是沿對角線的五次完成渡河;事實上,小舟容納b人(大於4的偶數),則有b+1至(3b/2 – 2)之土人(或傳教士)五次即可全部過河。如果小舟所能容納的人數是奇數,則對角線解往往不是最佳解。如果小舟所能容納的人數是大於3的奇數,而恰比土人(或傳教士)人數少一,則最佳解是七次可渡河。

參考資料

1.陳懷書著 數學遊戲大觀 商務印書館

2. D. A. Kordemsky, 359 Mathematical Recreations,凡異出版社,本書另有中文版凡異代銷。

3. H. E. Dudeny, 536 Puzzles & Curious Problems, Charles Scribner’s Sons, N.Y.

4.R.Fralley,K.L.Cooke & P. Detrick, Graphical solution of difficult crossing puzzles, Mathematics Magazine, May, 1966.

5.M.Gardner,”Mathematical Games”, Scientific American, p 18~24, March, 1980.

7 回應 針對 “渡河問題”

  1. 匿名訪客 寫道:

    写的不错

  2. scl 寫道:

    “写的不错”在數學Ph.D所評殊屬難得!
    希望能引起18歲以下動動腦,寫點回應!!

  3. 北投埔 寫道:

    原來是學長的同學!!謝謝誇獎!!學長們愛護學弟!!

    http://tw.myblog.yahoo.com/sclchiche/article?mid=2332&next=2311&l=f&fid=12

  4. 北投埔 寫道:

    渡河問題是數學遊戲, 但這種遊戲在第二次世界大戰中被美國軍方拿來成為作業研究(opration research), 變成科學管理重要的一支, 舉凡生產製程, 工作排程, 等等都會使用這類技術.

    所以遊戲也會成為正當行業!!

  5. Josephine Grosch 寫道:

    http://taipics.com/

    這個網址有非常多台灣早期日據時代原住民所拍攝的照片, 一定要看, 網站是外國人設.

  6. 匿名訪客 寫道:

    哇, 太精彩了

    US Consular Report on Events in Taiwan after 2.28

    http://www.froginawell.net/china/2007/05/us-consular-report-on-events-in-taiwan-after-228/

    228與葛超智

  7. 小周 寫道:

    你的解法與以前交大某教授(普渡大學博士)人工智慧課程中的解法蠻相近的!

留下回應

留言內含太多URL、廣告常見字,可能被系統視為廣告而扣住不顯示,請待版主解除。或寫私信給板主

本Blog其他隨機文章(五篇)

  • U-2:U. S. Naval Medical Research Unit 2美國海軍第二醫學研究所
  • 工研酢是聯合工業研究所的研發產品嗎?
  • 《中美技術》1954~1989
  • 介紹《東方台湾語辞典》――台語運動
  • 台灣電力株式會社社友會