『川渡り』

　今回のテーマは、船を川を渡って運ぶ問題です。

今、川のこちら岸に４隻の船Ａ，Ｂ，Ｃ，Ｄがあります。 今回の目的はこの４隻の船を全て向こう岸に運ぶことです。 　　　　　 川　 船Ａ　｜ ~ ~ ~ ~｜ 　　　｜ ~ ~ ~ ~｜ 船Ｂ　｜ ~ ~ ~ ~｜ 　　　｜ ~ ~ ~ ~｜ 船Ｃ　｜ ~ ~ ~ ~｜ 　　　｜ ~ ~ ~ ~｜ 船Ｄ　｜ ~ ~ ~ ~｜ 　　　｜ ~ ~ ~ ~｜ 船は１隻ずつ運ぶこともできるし、２隻を同時に運ぶこともできます。 ただし、２隻を同時に運ぶ場合は、遅いほうの船と同じ時間がかかります。 【問題１】 　船が川を渡るには、それぞれ１分、３分、６分、９分かかるとします。 さて、船を全て運ぶのにかかる最短時間を求めてください。 またその手順を示してください。 【問題２】 　それぞれの船が川を渡るには、ａ分、ｂ分、ｃ分、ｄ分かかるとします。 ただし、ａ≦ｂ≦ｃ≦ｄとする。 船を全て運ぶのにかかる最短時間を求めてください。 【問題３】 　今度は船がＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆの６隻、あるとします。 それぞれの川を渡るのにかかる時間は、２分、７分、９分、１１分、１４分、１５分であるとします。 船を全て運ぶのにかかる最短時間を求めてください。 【問題４】 　今度は船がＡ1〜Ａ2nの２ｎ隻、あるとします。 それぞれの川を渡るのにかかる時間は、ａ1、ａ2、・・・ａ2n分であるとします。 ただし、ａ1≦ａ2・・・≦ａ2nとする。 船を全て運ぶのにかかる最短時間を求めてください。 ※船の数が奇数の場合も、Ａ1、Ａ3で渡って、Ａ1でもどり、その後、問題４の手順をとれば最短時間が求められます。

参考文献：ピーター・フランクル 著「数学パズル塾」（朝日文庫）

　解答用紙はこちらです。　【寄せられた解答】

　◆パズル問題へもどる

　数学の部屋へもどる