河渡りの問題１

 　河渡りの問題は、東洋では西暦紀元前からあったといわれ、西洋でも８世紀のA．Alcuin（アルクイン）までさかのぼることができるので、きわめて古いパズルであるといえる。
※Alcuin（アルクィン、735？～ 804年）はイングランドのヨーク出身の修道士、神学者である。／アングロ・サクソン人で長年ヨークにある学校の教師として勤めたのち、カール大帝のフランク王国の教会制度と教育制度の相談役を務めた。769年からはトゥールの司教となり、聖マルティヌス（サン・マルタン）修道院の院長であった。
　アルクインの問題は次のようなものである。
　オオカミとヤギを連れ、キャベツの籠を持った男が、川を舟で渡ろうと思った。しかし、舟には男以外にどれか一つしか積むことができない。ところが、男がいないとオオカミはヤギを食うし、ヤギはキャベツを食べてしまう。どうしたら無事に渡れるだろうか。
　この解は２通りあるが、その一つをしめすと、
(1)ヤギを渡す。(2)男だけ戻ってくる。(3)オオカミを渡す。(4)ヤギを連れて戻る。(5)キャベツの籠を渡す。(6)男だけ戻ってくる。(7)もう１度ヤギを渡す。以上7回河を渡ることで目的が達せられる。
　この問題を、さらに複雑にしたのは16世紀のTartaglia〔タルターリア、1500～1557年頃〕である。
※Tartaglia〔タルターリア、1499か1500～1557年〕はルネサンス期イタリアの数学者、技術者。少年期に口に受けた傷によって、どもりを意味するイタリア語に由来するニックネーム、タルターリアを与えられた。正式の教育はほとんど受けなかったが、持ちまえの勤勉さで数学的知識をものにした。数学上の独創的業績としては、1535年の三次方程式の解の発見が第1にあげられる。
　彼は嫉妬深い夫婦の河渡り問題を提起した。曰く、「３組の夫婦が河を舟で渡ろうと思った。舟には一度に２人しか乗ることができない。ところが、かれらはきわめて嫉妬深く、妻は自分の夫が対でない他の夫人と一緒にいることは我慢がならない。夫の方も自分の妻が対でない他の男と一緒にいることは許さない。どうしたらトラブルなしに河を渡ることができるだろうか。」
　
　これは11回河を渡る必要がある。３組の夫をＡ、Ｂ、Ｃで、その妻をａ、ｂ、ｃで表すと、付図の解はその一例である。
　河渡りが無事に出来るかどうかは、夫婦の組み数と舟の定員によって決まってくる。舟の定員が夫婦のくみ数が何組あっても河渡りは可能である。つまり、一組の夫婦が船頭役になって、他の夫婦を対岸に送り届けれはよいからである。
　M.kraitchik（クライチック）という人がその著書の中で、これを付表のようにまとめている。この表で判るように、ボートの定員が２名である場合に可能なのは３組までで、４組になるとこの条件では渡ることができない。