川渡り問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

川渡り問題(かわわたりもんだい)は、川岸にいる一団を特定の条件を満たしながら対岸に渡すパズルである。通常論理パズルに分類される。

川に架かっている橋を渡る問題に関しては一筆書きを参照。

ルール

  • 川岸にいる一団を対岸に渡す。
  • 川を渡る手段は小船だけであり、小さいので数人しか乗れない。
  • 特定の組み合わせがどちらかの岸にできてはいけない。
    多くは「○○がいない状態で□□と△△を一緒にしてはいけない」という形で与えられる。

例題

簡単な例

1人の大人と2人の子供が岸にいる。ボートが1台あるが大人1人か子供2人までしか乗れない。全員が川を渡るにはどうすればよいか?

狼とヤギとキャベツ

この問題は、8世紀にカンタベリーの大主教が提示した問題といわれている。

オオカミヤギを連れキャベツを持った農夫が川岸にいる。川にはボートがあるが農夫の他には動物一頭かキャベツ一個しか乗せられない。農夫がいなければオオカミはヤギを襲うし、ヤギはキャベツを食べてしまう。すべてを無事に対岸に渡すにはどうしたらよいか?

オオカミを狐、ヤギをガチョウ、キャベツを豆の袋に替えた問題もある。

宣教師と先住民

3人の宣教師と3人の先住民が川岸にいる。川には2人まで乗れるボートが1艘ある。ボートをこげるのは宣教師の1人と先住民の1人だけである。また、どちらかの岸で先住民の数が宣教師の数より多くなると、先住民は反旗を翻し宣教師に襲い掛かる。全員が無事に対岸に渡るにはどうしたらよいか?

考え方

禁止されている状態にならないように移動させていればそのまま解けてしまうこともある。

他には

  • ボートをこげる人を確保する
  • 対岸に渡した人(物)をもう一度連れて帰る

といった点を考えるとうまくいくことが多い。

バリエーション

一団の条件を変えれば新しい問題を作ることができる。嫉妬深い(自分がいないところで妻が他の男といるのが嫌という)夫婦たちの問題などが有名である。

また、

  • 川の途中に中州を設ける。(人や荷物を置くことができる)
  • ボートの定員や台数を変える。

等で新しい問題を作ることもできる。

例題の解答

簡単な例
  1. 子供2人が渡る。
  2. 子供1人が戻る。
  3. 大人が渡る。
  4. 子供1人が戻る。
  5. 子供2人が渡る。
農夫の問題
  1. ヤギを連れて渡る。
  2. 戻る。
  3. オオカミを連れて渡る。
  4. ヤギを連れて戻る。
  5. キャベツを持って渡る。
  6. 戻る。
  7. ヤギを連れて渡る。
宣教師と先住民
簡略化のため、宣教師をm・先住民をiで表す。また、ボートをこげる人を大文字で表す。
  1. Ii が渡り、I が戻る。
  2. Ii が渡り、I が戻る。
  3. Mm が渡り、Mi が戻る。
  4. MI が渡り、Mi が戻る。
  5. Mm が渡り、I が戻る。
  6. Ii が渡り、I が戻る。
  7. Ii が渡る。