8世紀の教材「川渡り問題」に挑戦

樹形図を使って解く問題を取り上げたい。「川渡り問題」という論理パズルの一種がある。もともとは8世紀にフランク王国のシャルルマーニュ（別名カール大帝）の相談役だった修道士のアルクィンが、皇太子のための教材として考案したといわれる問題だ。川渡り問題にはいろいろなパターンがあるが、ここでは初級編に挑戦していく。

問題：「川岸に父親と2人の子どもがやって来た。向こう側に渡りたいが、あいにく船は一艘しかなく、船頭もいないため、自分たちで漕がなければならない。しかし重量制限があり、1回に乗れるのは父親である大人1人か、あるいは子ども2人まで。さて、どういう順序で船に乗れば全員が向こう岸に渡れるか？」――。

場合分けをしていこう。ポイントは表記のルールを決めて、わかりやすく情報を図式化することだ。必要な情報は3つで、こちら岸と向こう岸という情報、大人と子ども2人、そして船のそれぞれの位置を示す情報だ。

最初に考えられるのは、「大人1人で渡る」「子ども1人で渡る」「子ども2人で渡る」の3パターンだ（図参照）。船は1艘しかないので、誰かが必ず漕いで戻ってこなければならず、したがって次に進むためには、1人で渡るという選択肢は消える。つまり、最初は子ども2人で渡るしかないというわけだ。