クイズ 「狼と山羊とキャベツ」
栗原正純
電気通信大学 情報通信工学科
（2008/05/30）
2015/10/1
1
2015/10/1
2
船に乗る組み合わせ
2015/10/1
3
食べ（食べられ）てしまう組み合わせ
男がいなくても安全
な組合せ
2015/10/1
4
問題 1/2
• 川の左岸から右岸へ、男が自分自身以外に
１つのものしか運べない船を用いて、狼、山
羊、キャベツを安全に運ぶには、どのような
順序で運べばよいかを考えよう。
• ただし、男が一緒にいないと、「狼は山羊を食
べてしまう」、さらに、「山羊はキャベツを食べ
てしまう」という条件がある。
2015/10/1
5
問題 2/2
• 問１．どのような順序でそれぞれを運べばよ
いか、具体的な手順（方法）を示せ。
• 問２．少なくとも船を何回利用する必要がある
かを示せ。すなわち、最小利用回数を示せ。
• 問３．最小利用回数で実行できる手順は何通
りあるか？それらの手順をすべて示せ。
2015/10/1
6