頭の体操（IQ120）：川渡り問題

先週紹介した、「二つの円と直線に接する円」を見つける問題と同じく、エンジニアの面接で良く使っていたのが、「川渡り問題」です。

この問題が素晴らしいのは、バラエティがいくつもある点で、それらを組み合わせて面接方式で解いてもらうと、その人の論理的思考能力とかコミュニケーション・スキルを測ることが可能です。

まずは、問題を解くことだけに興味のある人のために、問題だけを書いてみます。

問題１：大人一人と子供二人が、手漕ぎの船で対岸まで渡ろうとしています。船は小さく、子供であれば二人乗ることができますが、大人が一人乗るとそれで一杯になってしまいます。船は一つしかなく、大人も子供も船が漕げるとした場合、どうやれば全員で対岸に渡ることが出来るでしょう？

問題２：宣教師が３人と人喰い人種３人が、二人乗りの手漕ぎの船で対岸まで渡ろうとしています。人食い人種は宣教師が自分たちと同じ人数かそれ以上いる時には大人しいのですが、自分たちの方が人数が多くなると、宣教師を食べてしまいます。宣教師が食べられないように、対岸に渡るにはどうしたら良いでしょう？

問題３：猟師が狐と山羊とキャベツと一緒に、船で対岸まで渡ろうとしています。しかし船が小さいため、猟師と一緒に船に乗せることが出来るのは、どれか一つだけです。狐は猟師が見ていないと山羊を食べてしまい、ヤギは猟師が見ていないとキャベツを食べてしまいます。山羊やキャベツが食べられないように対岸に渡るには、どうしたら良いでしょう？

問題４：４人の人が真夜中に川にかかった吊り橋を渡ろうとしています。吊り橋に同時に乗ることが出来るのは最大二人です。それぞれの人の足の速さは大きく異なり、その橋を渡るにはそれぞれ１分、２分、５分、１０分が必要です。真っ暗なため、懐中電灯が必要ですが、一つしかないため、二人で渡る際には手を繋いで、遅い人に合わせたスピードで渡る必要があります。懐中電灯の電池が１７分しか残っていない場合、どうやったら全員で対岸に渡ることが出来るでしょう？

問題５：オリジナルの川下り問題を作ってください。

論理的思考に自信がある人、パズル好きの人は、ここで読むのをやめて、上の問題を解いてみてください。これまでどの問題も見たことがなくて、ヒントなしで解けるとしたら、かなり頭の良い証拠だと思います（IQ=120ぐらい）。

この問題を面接で使う場合、その人が既にこの問題を解いたことがある可能性が十分にあるため注意が必要です。あまりにもスラスラと解くようであれば、別の問題に移った方が良いと思います。

ちなみに、川渡り問題は、日本では多胡輝先生の「頭の体操」に紹介されたことで広く知られるようになりましたが、最も古い文献としては８世紀にラテン語で書かれたものがあるそうです。上の絵は、その古文書の作者とされる Flaccus Albinus Alcuinus (真ん中の人）を描いたものです。

問題１の回答

様々なアプローチがありますが、一番最後にはどうなるかを考えて逆算するのが、このケースでは一番簡単です。最後に大人一人だけ、もしくは、子供一人だけが渡ることは考えられないので（誰かが船で戻る必要があります）、最後は必ず、子供二人が渡ることが分かります。そして、その前のステップでは、対岸に大人一人と子供一人がいて、子供一人が船でもう一人を迎えに行くことも自明です。

その前のステップも、子供一人が対岸にいるところに、大人一人が向かうことも自明です（そうでなければ、次のステップが無駄になります）。つまり、対岸に子供が一人だけいる状況をなんとか作れば良いのです。

そんな状態を作るには、最初に子供二人が対岸に向かい、一人がこちら側に戻って来れば良いことが分かります。つまり、手順を図にすると、以下のようになります（赤が大人、青が子供、左岸から右岸に渡り、縦軸は手順です）。

問題２以降の回答は有料です。ちなみに、この問題は私のメルマガ（週刊 Life is beautiful、毎週火曜日発行、月額864円）の５月７日号からの引用です。