传教士和吃人恶魔问题

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

问题

编辑

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

解答

编辑
 
过河问题解决方案的图
  • 第一步、两个恶魔过去: 结果此岸: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 种。

亦有将吃人恶魔以食人族代换的版本,不影响问题解法。

参见

编辑