渡河問題二進制解法筆記

 

　　偶爾翻開李友耕著的《進位制與數學遊戲》，始知道原來小時候常見到的一類趣味智力問題：渡河問題是可以使用二進制來幫助求解的。百忙中，做了小小筆記，期能幫助自己記着這種解法的原理。

 

問題一

一位農民帶着一頭狗、一頭雞和一小籮白菜來到了河的北岸，準備利用岸邊的一隻小船過河。但船很小，每次他只能帶一樣東西過河。問題是，他不在岸上看管的時候，狗會咬雞，或者雞會吃菜，唯一不會發生的是狗咬菜。農民該如何安排過河方案，既把三樣東西都無損地全帶到南岸，又使小船來回的次數最少？

 

 

解法：問題涉及四樣東西，以二進數制來幫助求解，需用到四位二進制數：從四位二進數的最高位起，依次表示人、狗、雞、菜，當某物在北岸，以0表示；當某物在南岸，以1表示，故此這個渡河問題的努力目標就是從0000演變到1111。下圖是實際的推演：

 

 

 

 

問題二

兩位警察到某地辦事，回程時於途中聽到老人的呼救聲，發現是兩個歹徒在毆打兩位老人。警察立即制服了歹徒。兩位警察帶着兩位老人，押着兩個歹徒返回警局，但必須渡過一條小河，然而渡口上只有一條小船，它一次只能容納兩個人。這六個人都會划船，但歹徒不能沒有警察看守（不能讓歹徒單獨划船或僅讓歹徒留在某岸上），不然會行兇或逃跑；所以也不能讓歹徒和老人一同划船；事實上，為防歹徒聯合作惡，當只有一位警察在岸時，警察可用手銬把兩個歹徒銬起來。

請問，怎樣安排才能使他們以最少的次數安全地全部過河呢？

 

解法：問題涉及六個人物，以二進數制來幫助求解，需用到六位二進制數。解法可仿照問題一的辦法，而當明白到這類問題的對稱性質，可以使用「前後（首尾）夾擊」的方式來求解。下圖是實際的推演：