動物親子渡河問題(3)の解答例を示します。
問題(3)の解
8頭無事に川を渡れない。
親トラ(A)、子トラ(a)、親ライオン(B)、子ライオン(b)、親ヒョウ(C)、子ヒョウ(c)、親オオカミ(D)、子オオカミ(d)とする。
8頭が渡河できるとして、左岸から右岸への渡河、また右岸から左岸への渡河に番号をつけ、これを渡河番号ということにする。すると、奇数番目の渡河をしたときは右岸に、偶数番目の渡河をしたときは左岸にボートがあることになる。
そこで、初めて右岸に3頭以上の親がいる渡河番号を2k+1とする。ボートに2頭しか乗れないので、渡河番号2k-1では、右岸に1頭または2頭の親がいたことになる。