傳教士和吃人惡魔問題
外觀
此條目沒有列出任何參考或來源。 (2020年2月5日) |
傳教士和吃人惡魔問題是一則古老的智力遊戲題。
問題
[編輯]有三個傳教士和三個惡魔要渡過一條河,而河中有一條船,船只能容納兩個人。而且在任何一個地方(無論是岸邊還是船上),如果惡魔的數量多於傳教士的數量,惡魔就會吃掉傳教士。怎樣才能讓這些人全都安全過河?(來回的船上都必須要有人操作)
解答
[編輯]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/JealousHusbandsProblemSolutionGraphic.png/220px-JealousHusbandsProblemSolutionGraphic.png)
- 第一步、兩個惡魔過去: 結果此岸:3 傳教士,1 惡魔,彼岸:0 傳教士 2 惡魔
- 第二步、一個惡魔回來;結果此岸:3 傳教士,2 惡魔,彼岸:0 傳教士 1 惡魔
- 第三步、兩個惡魔過去;結果此岸:3 傳教士,0 惡魔,彼岸:0 傳教士 3 惡魔
- 第四步、一個惡魔回來;結果此岸:3 傳教士,1 惡魔,彼岸:0 傳教士 2 惡魔
- 第五步、兩個傳教過去;結果此岸:1 傳教士,1 惡魔,彼岸:2 傳教士 2 惡魔
- 第六步、一個傳教士一個惡魔回來;結果此岸:2 傳教士,2 惡魔,彼岸:1 傳教士 1 惡魔
- 第七步、兩個傳教士過去;結果此岸:0 傳教士,2 惡魔,彼岸:3 傳教士 1 惡魔
- 第八步、一個惡魔回來;結果此岸:0 傳教士,3 惡魔,彼岸:3 傳教士 0 惡魔
- 第九步、兩個惡魔過去;結果此岸:0 傳教士,1 惡魔,彼岸:3 傳教士 2 惡魔
- 第十步、一個惡魔回來;結果此岸:0 傳教士,2 惡魔,彼岸:3 傳教士 1 惡魔
- 第十一步、兩個惡魔過去;結果此岸:0 傳教士,0 惡魔,彼岸:3 傳教士 3 惡魔
上面第一步可以有個變體:
- 第一步、一個傳教士和一個惡魔過去: 結果此岸:2 傳教士,2 惡魔,彼岸:1 傳教士 1 惡魔
- 第二步、一個傳教士回來;結果此岸:3 傳教士,2 惡魔,彼岸:0 傳教士 1 惡魔
上面第十步也可以有個變體:
- 第十步、一個傳教士回來;結果此岸:1 傳教士,1 惡魔,彼岸:2 傳教士 2 惡魔
- 第十一步、一個傳教士一個惡魔過去;結果此岸:0 傳教士,0 惡魔,彼岸:3 傳教士 3 惡魔
因此,對於三個傳教士、三個惡魔的情況,共有 4 種不同的解法;
變體
[編輯]如果船可以同時乘坐 2 位乘客時,傳教士和惡魔都為 2 時,也有 4 種不同解法。但傳教士和惡魔數都為 4 時沒有解。 如果船可以同時乘坐 3 位乘客時,傳教士和惡魔數都為 2,3,4,5時都有解法,其唯一解數分別為 12,54,72,216 種。 如果船可以同時乘坐 4 位乘客時,傳教士和惡魔數為任意相同的數都有解法。比如 5 和 6 時,其唯一解數分別為 1200 和 3600 種。
亦有將吃人惡魔以食人族代換的版本,不影響問題解法。