危ない家族
 
ある家族がいます。
この家族は舟を使って川の向こう岸へわたろうとしています。
舟は１艘(そう)しかなく、１度に２人まで乗ることができます。
家族は父、母、息子１、息子２、娘１、娘２、メイド、犬の８人(犬も１人と数えます)であり、またこの舟をこげるのは父か母かメイドの３人だけです。
さぁ、そしてこの家族、ぢつは！とっても危険な家族なんです。
まず父は、母がいないと娘を殺してしまいます。
また母は、父がいないと息子を殺してしまいます。
そしてきわめつけ。
犬は、メイドがいないと家族をみんな殺してしまいます。
 
誰も死ぬことなく川をわたりきるにはどうすればよいでしょうか？
 
解答
最短で「17」回かかります。
まず、舟をこぐことができるのは父、母、メイドの３人です。
父が舟に乗ると息子が殺されてしまいす。
よって息子も同乗しなければなりません。
しかし、一度に乗ることのできる人数は２人までなので、息子２人のどちらかは殺されてしまいます。
よって、最初に父が舟に乗ることはありません。
同様に母も舟に乗ることはありません。
ゆえに最初は
  1. メイドと犬が舟に乗り向こう岸へわたることになります。
    （舟を使ってわたった先を向こう岸、最初にいるところを岸と呼びます）
    向こう岸（舟）：メイド、犬
    岸：父、息子、息子、母、娘、娘
    舟をこぐことができるのはメイドのみです。
    犬を同乗させては意味がないので
  2. メイドが舟に乗り岸に戻ってくる。
    向こう岸：犬
    岸（舟）：父、息子、息子、母、娘、娘、メイド
    向こう岸に犬がいるためメイドが舟に乗らなければなりません。
    父、母のどちらかが乗ると息子か娘が殺されるので、この父、母は岸に待機します。
    メイド１人で乗っても意味がないので
  3. メイドと娘が舟に乗り向こう岸へわたる。
    向こう岸（舟）：娘、メイド、犬
    岸：父、息子、息子、母、娘
    （同乗するのは息子でもよいのですが、ここでは娘にします）
    舟をこぐことができるのはメイドのみです。
    犬を連れて行かなければ娘が殺されるので
  4. メイドと犬が舟に乗り岸に戻ってくる。
    向こう岸：娘
    岸（舟）：父、息子、息子、母、娘、メイド、犬
    舟をこぐことができるのは父、母、メイドです。
    メイドと犬が舟に乗っても意味がないので父か母が舟に乗ることになります。
    父が乗ためには息子２人を連れて行かなければなりません。
    舟は２人乗りなので不可能です。
  5. 母と娘が舟に乗り向こう岸へわたる。
    向こう岸（舟）：母、娘、娘
    岸：父、息子、息子、メイド、犬
    舟をこぐことができるのは母のみです。
    娘を連れて行っても意味がないので
  6. 母が舟に乗り岸に戻ってくる。
    向こう岸：娘、娘
    岸（舟）：父、息子、息子、母、メイド、犬
    舟をこぐことができるのは父、母、メイドです。
    メイドが乗るためには犬も同乗しなければなりません。
    向こう岸で娘を殺さないためにメイドが犬を連れて帰らなければなりません。
    そうすると意味がないので、メイドと犬は岸に待機します。
    父が乗ると向こう岸の娘が殺されてしまいます。
    また岸にいる息子２人も母によって殺されてしまいます。
  7. 父と母が舟に乗り向こう岸へわたる。
    向こう岸（舟）：父、母、娘、娘
    岸：息子、息子、メイド、犬
    舟をこぐことができるのは父、母のみです。
    岸にいる息子の命を守るため父が舟に乗る必要があります。
    母が同乗しても意味がないので
  8. 父が舟に乗り岸に戻ってくる。
    向こう岸：母、娘、娘
    岸（舟）：父、息子、息子、メイド、犬
    舟をこぐことができるのは父とメイドのみです。
  9. ここで２通りの考えができます。
    それは父と息子の組合せとメイドと犬の組合せです。
    父と息子がの組合せで行くと
    向こう岸（舟）：父、息子、母、娘、娘
    岸：息子、メイド、犬
    となります。
    岸にいる息子の命を守るため父は戻ってこなければなりません。
    向こう岸にいる息子の命も守るために母が同乗する必要があります。
    そうすると
    向こう岸：息子、娘、娘
    岸：父、息子、母、メイド、犬
    となります。
    舟をこぐことができるのは父、母、メイドです。
    メイドが乗るためには犬も同乗しなければなりません。
    そうすると向こう岸にいる息子と娘を殺さないためにメイドが犬を連れて帰らなければなりません。
    そうすると意味がないので、メイドと犬は岸に待機します。
    父と母で舟に乗っても意味がありません。
    父と息子（または父だけ）で舟に乗ると向こう岸にいる娘が殺されてしまうので父は岸に待機します。
    母だけで舟に乗るとむこうぎしの息子が殺されてしまうので母も岸に待機します。
    そうするとこれ以上進められなくなってしまうので、次はメイドと犬の組合せで行く必要があります。
  10. メイドと犬が舟に乗り向こう岸へわたる。
    向こう岸（舟）：母、娘、娘、メイド、犬
    岸：父、息子、息子
    舟をこぐことができるのは母、メイドのみです。
    メイドが乗るためには犬も同乗しなければなりません。
    そうすると意味がないのでメイドと犬は向こう岸に残ります。
    母１人で行くか母と娘の２人で行くかのどちらかになります。
    目的は全員が向こう岸へわたることです。
    向こう岸には１人でも多く残しておきたいので
  11. 母が舟に乗り岸に戻ってくる。
    向こう岸：娘、娘、メイド、犬
    岸（舟）：父、息子、息子、母
    舟をこぐことができるのは父、母のみです。
    母１人で行っても意味がありません。
    父が舟に乗るためには岸にいる息子の命と向こう岸にいる娘の命を守るために母も同乗する必要があります。
  12. 父と母が舟に乗り向こう岸へわたる。
    向こう岸（舟）：父、母、娘、娘、メイド、犬
    岸：息子、息子
    舟をこぐことができるのは父、母、メイドです。
    メイドが乗るためには犬も同乗しなければなりません。
    そうすると岸にいる息子を殺さないためにメイドが犬を連れて帰らなければなりません。
    そうすると意味がないので、メイドと犬は向こう岸に待機します。
    岸にいる息子の命と向こう岸にいる娘の命を守るために父１人で乗るか、父と母で乗るかの２通りの組合せがあります。
    父と母で舟に乗っても意味がないので
  13. 父が舟に乗り岸に戻ってくる。
    向こう岸：母、娘、娘、メイド、犬
    岸（舟）：父、息子、息子
    舟をこぐことができるのは父のみです。
    父１人で乗っても意味がないので
  14. 父と息子が舟に乗り向こう岸へわたる。
    向こう岸（舟）：父、息子、母、娘、娘、メイド、犬
    岸：息子
    舟をこぐことができるのは父、母、メイドです。
    父が舟に乗るためには息子か母が同乗しなければなりません。
    息子が同乗しても意味がありません。
    母が同乗すると母は向こう岸にいる娘の命を守るために戻って来なければなりません。
    向こう岸にいる息子の命を守るために父も同乗しなければなりません。
    つまり父と母が舟に乗って岸に戻ってきてもまたその２人で向こう岸へわたらなければならないため、意味がありません。
  15. メイドと犬が舟に乗り岸に戻ってくる。
    向こう岸：父、息子、母、娘、娘、メイド、犬
    岸（舟）：息子、メイド、犬
    舟をこぐことができるのはメイドのみです。
    岸にいる息子の命を守るためにメイド一人で帰ることは許されません。
    また、犬を連れて帰っても意味がありません。
  16. メイドと息子が舟に乗り向こう岸へわたる。
    向こう岸（舟）：父、息子、息子、母、娘、娘、メイド
    岸：犬
    岸に行くことができるのはメイドのみです。
  17. メイドが舟に乗り岸に戻ってくる。
    向こう岸：父、息子、息子、母、娘、娘
    岸（舟）：メイド、犬
    舟をこぐことができるのはメイドのみです。
    １人で帰っても意味がないので
  18. メイドと犬が舟に乗り向こう岸へわたる。
    向こう岸（舟）：父、息子、息子、母、娘、娘、メイド、犬
    となってクリアです。
 
整理すると
 
  1. メイドと犬が舟に乗り向こう岸へわたる。
  2. メイドが舟に乗り岸に戻ってくる。
  3. メイドと娘が舟に乗り向こう岸へわたる。
  4. メイドと犬が舟に乗り岸に戻ってくる。
  5. 母と娘が舟に乗り向こう岸へわたる。
  6. 母が舟に乗り岸に戻ってくる。
  7. 父と母が舟に乗り向こう岸へわたる。
  8. 父が舟に乗り岸に戻ってくる。
  9. メイドと犬が舟に乗り向こう岸へわたる。
  10. 母が舟に乗り岸に戻ってくる。
  11. 父と母が舟に乗り向こう岸へわたる。
  12. 父が舟に乗り岸に戻ってくる。
  13. 父と息子が舟に乗り向こう岸へわたる。
  14. メイドと犬が舟に乗り岸に戻ってくる。
  15. メイドと息子が舟に乗り向こう岸へわたる。
  16. メイドが舟に乗り岸に戻ってくる。
  17. メイドと犬が舟に乗り向こう岸へわたる。