読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Haskellでクイズ「嫉妬深い男たち」を解く(1)

1.嫉妬深い男たち

よく知られている問題だが、旅行をしている3組のカップルがいる。

このカップルたちは、飛行機や車を使った旅行には飽きてしまったので、旧道が残る東海道を徒歩で旅行していた。

それぞれのカップルは仲は良いのだが、唯一の欠点は、どの男性も嫉妬心が強く、相手の女性が常に自分と一緒にいるか、離れている場合でもほかの女性たちだけ(男性が混じっているのはダメ)といる場合しか認めないことであった。

旧道を進むうちに、少し幅のある川に出くわした。幸いなことに、川には、一艘の小舟が用意されていたので、このカップルたちはこの舟を利用して、対岸に渡ることにした。

小舟には最大で二人まで乗れることになているのだが、男性たちの嫉妬心を掻きたてることなく、三組のカップルが対岸に渡るためには、どうしたらよいかいうのが今回の問題である。

なお、舟の乗換には時間がかからず、先ほど述べた都合の悪い状況が生じても、男性は嫉妬心を抱かないものとする。

解を求めるまで、いくつかの考察をしてみよう。

2.とりあえず解を求めてみる。

川にたどり着いた状況は

      男1  女1    |              |
      男2  女2    |              |
      男3  女3    |              |

求める解は

                  |              |    男1  女1
                  |              |    男2  女2
                  |              |    男3  女3

である。

とりあえず、男性が一人乗船した状況を考える。

           女1    |     男1      |
      男2  女2    |            ->|
      男3  女3    |              |

上の状況は、「男1」の相手の女性「女1」が他の男性と川岸に残るので好ましい状況ではない。従って、一人乗船する場合には、「女1」が小舟に乗ることとなる。

しかし、一人の乗船では、この人が行って帰ってくるだけとなり、何の進展もない。

そこで、二人乗船することを考える。カップルで乗船するのも許されるが、ここでは、女性二人が乗船するにする。

      男1         |     女1      |
      男2         |     女2    ->|
      男3  女3    |              |

対岸につくと、女性一人が岸に上がり、一人が戻ってくることになる。例えば次のようになる。

      男1         |     女1      |      
      男2         |<-            |         女2
      男3  女3    |              |

さて、次はどうしたらよいだろうか?戻ってきた女性とその相手の男性とで舟に乗ってもらうことにすると次のようになる。

                  |    男1女1    |       
      男2         |            ->|         女2
      男3  女3    |              |

カップルが残り、岸にいた女性が戻ってくると次のようになる。

                  |              |    男1  女1
      男2         |<-   女2      |          
      男3  女3    |              |

次は、戻ってきた来た女性とその相手の男性で渡ることにする。

                  |              |    男1  女1
                  |    男2女2  ->|          
      男3  女3    |              |

男性の方が岸に上がり、女性はそのまま戻る。

                  |              |    男1  女1
                  |<-   女2      |    男2        
      男3  女3    |              |

ここまで来ると、後は簡単である。次は女性二人で舟に乗るか、カップルで舟に乗ればよい。戻ってくる舟には、一人で残っている人の相手の人が戻ってきて、最後に一緒に舟に乗ってあげればよい。

さて、上の説明で何か法則性のようなものは得られたであろうか?そのように思った人は、四組のカップル、五組のカップルに挑戦してください。