传教士和吃人恶魔问题

维基百科,自由的百科全书

传教士和吃人恶魔问题是一则古老的智力游戏题。

问题

有三个傳教士和三个惡魔要渡过一条河,而河中有一条船,船只能容納两个人。而且在任何一个地方(无论是岸边还是船上),如果惡魔的数量多于傳教士的数量,惡魔就会吃掉傳教士。怎样才能让这些人全都安全过河?(来回的船上都必须要有人操作)

解答

過河問題解決方案的圖
  • 第一步、兩個惡魔過去: 结果此岸: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 種。

参见