船のクイズの一般化

質問

先日、このサイトで面白いクイズを見つけたので（590136）、問題を一般化してみました。

------------------------------------------------------
船がn艘あり、これを船頭さんが一人で対岸まで移動します。
n艘の船は川を横切るのにそれぞれ1分、2分、4分、、、2^(n-1)分かかります。
船頭さんは1艘を運転し、もう1艘をその船に牽引することができます。
ただし、2艘を同時に移動する場合、そのスピードは遅い方の船のスピードになります。
また、船で元の岸に帰ってくる時間も考えなければなりません。
船を全て向こう岸まで移動するのに必要な最短時間Ｓn（分）を求めてください。
------------------------------------------------------

nを1から考えてみると、

n = 1 （1）のとき　　　　　　　Ｓ1 = 1
n = 2 （1,2）のとき　　　　　　Ｓ2 = 2
n = 3 （1,2,4）のとき　　　　　Ｓ3 = 7
n = 4 （1,2,4,8）のとき　　　　Ｓ4 = 15
n = 5 （1,2,4,8,16）のとき 　　Ｓ5 = 28
n = 6 （1,2,4,8,16,32）のとき　Ｓ6 = 52
　　　・
　　　・

そこでお聞きしたいのですが、

（１）Ｓ5、Ｓ6は、これで合っているでしょうか？
（２）Ｓnを一般式で表すことができるでしょうか？

どうか、よろしくお願いいたします。

回答No.7

ryn · ベストアンサー

n = 4 の場合からの類推で。
時間のかかる船２隻で一緒に移動するという方針で考えてみます。

１番遅い船にまぎれて２番目に遅い船を移動させたのに
そのどちらかで戻ってきては意味がありません。
したがって、先に1分、2分かかる船で移動しておきます。
具体的には

往路　　　　　　　復路
1-2　　　　　　　　1(or 2)
2^(n-2)-2^(n-1)　　2(or 1)
1-2　　　　　　　　-

で遅い２隻の船を移動させます。
ここまでで、合計 2^(n-1) + 5 分かかることになります。
残りは 1,2,…,2^(n-3) 分かかる船 2^(n-2)隻です。

したがって、
　S_n = S_(n-2) + 2^(n-1) + 5
という漸化式が成り立ちます。

n の偶奇で場合分けが必要なので、
とりあえず偶数の場合を見てみると
　S_n - S_(n-2) = 2^(n-1) + 5
　S_(n-2) - S_(n-4) = 2^(n-3) + 5
　　：
　　：
　S_8 - S_6 = 2^7 + 5
+)S_6 - S_4 = 2^5 + 5
――――――――――――――――
　S_n - S_4 = (2^5 + 2^7 + … + 2^(n-1)) + 5(n/2 - 2)

したがって、n が偶数で n≧4 のときは
　S_n = S_4 + (2^(n+1) - 32)/3 + 5(n/2 - 2)
　　　= (2/3)*2^n + (5/2)n - 17/3
のようになります。

同様にして n が３以上の奇数のときは
　S_n = (2/3)*2^n + (5/2)n - 35/6
となります。

最初の前提を証明できていないので、
2^(n-1) と 2^(n-3) を同時に移動させるなどのような
方法でもっと短い時間で移動する方法があれば、
上の議論は無意味になってしまいますが…。

お礼

こんばんは。
とても分かりやすくて、スッキリしたご回答をありがとうございました。最短時間を求めるアルゴリズムは、これ以外には私には想像もつきませんが、もっと画期的な方法があるのでしょうか？
ともあれ、このような明解な回答をいただいて、非常に満足しています。
本当にありがとうございました。

回答No.8

c6h6

No.3 , No.4のものです。

最初に1and2で移動、2で戻る
一番遅いand二番目に遅い船で移動、1で戻る
ということで2^(n-1)+5の時間をつかえば　遅い2隻がいなくなる。

奇数隻の場合、
Sn=2^(n-1) + 2^(n-3) + ・・・ + 2^1 +5(n/2 -1)

偶数隻の場合、
Sn=2^(n-1) + 2^(n-3) + ・・・ + 2^2 +5(n-1)/2 -2

というところまではわかったのですが、
2^(n-1) + ・・・ + のところを私には一般式にあらわすことができません。

お礼

ベンゼンさま、いや違いました、c6h6さま、再度のご回答をありがとうございます。
最初にご回答をいただいてから、あっという間にたくさんのご回答をいただき、やっと私の頭でも理解できました。解法のやり方としては、おっしゃられている通りだと思います。楽しい数時間でした。大変ありがとうございました。

補足

みなさま、たくさんのご回答をありがとうございました。数学カテゴリーは、その他（ライフ）に次いで私の好きなカテゴリーですが、いつも明解な回答を目にして、みなさまの頭脳にただただ尊敬の念を抱いています。私の悩みも解決しましたので、これで閉めさせていただきたいと思います。

たくさんの回答をいただいて、ポイントをおつけするのは、いつも悩むのですが、非常にわかりやすく説いてくださったrynさまに２０ポイント、まっ先にＳ5、Ｓ6を検算し、偶数、奇数の場合分けが必要と予測してくださったfushigichanさまに１０ポイントをつけさせていただきましたが、ほかの方々にもポイントをおつけしたい気持ちでいっぱいです。

みなさま、大変ありがとうございました。またいつか、しょーもない質問をすると思いますが、どうぞよろしくお願いいたします。

回答No.6

ticky

こんばんは。
n>=4において、
S_n＝5＋２^(n-1)＋S_(n-2)
が成立しているようです。
この式は、始めに1分かかる船と2分かかる船で行って、1で戻ってきて、一番遅い船と次に遅い船で行って、
2分かかる船で戻ってくると、
後は、1分かかる船から2^(n-2)分かかる船までが残っている・・・という方法を採用した場合です。

これに基づくと、
S_1＝１
n>=１で、
S_(2n)＝4/3(1/4-(1/4)^n)*2^(2n+1)＋5(n-1)＋2
S_(2n+1)=4/3(1/4-(1/4)^n)*2^(2n+1)＋5(n-1)＋7
だと思います。

最速かどうかも分からないし、計算が合っているかどうか不安ですが。

お礼

こんばんは。
途中の過程が不明で、どうやって導かれた式かわかりませんでしたが、S_(2n)は合っているようですね。S_(2n+1)は私の検算の仕方が悪いのか、答えが一致しませんでしたが、考え方は、理解できました。

＞　最速かどうかも分からないし、

いえ、これが最速だろうと思います。って、私が太鼓判押しても説得力はありませんが、、、。

ご回答をありがとうございました。

回答No.5

TK0318

ｎ＝２ｋ、２ｋ－１の時で場合分けします。

＊これは船が２隻増えた場合
・１，２で渡る
・１で帰る
・ａｎ、ａ（ｎー１）で渡る
・２で帰る
となりＳｎはＳｎ－２に比べてａｎ＋５分余計にかかります。

よって
Ｓ２ｋ＝Ｓ２（ｋ－１）＋ａ２ｋ＋５
Ｓ２ｋ－１＝Ｓ（２ｋ－３）＋ａ（２ｋ－１）＋５
ａ２ｋ＝２＊４＾（ｋ－１）
ａ２ｋ－１＝４＾（ｋ－１）
ａ１＝１
ａ２＝２
となります。

あとは等比数列ですが・・・私の実力では解けん＾＾；
多分これでいけると思います・・・

お礼

こんばんは。いつもお世話になります。

考え方は分かりやすくて、私にも理解できました。

＞　あとは等比数列ですが・・・私の実力では解けん＾＾；

またまたご冗談を。TK0318さんの実力からして、「解けるけど、面倒くさいから、自分で解いてね」というメッセージだと理解しました。☆＾＾☆

ご回答をありがとうございました。

回答No.4

c6h6

Oh!　なるほどー
すでに置いてきた船で帰ってきてもいいんですね。
ちょっと考えてみます。

お礼

下のお礼でも申し上げましたが、そういうことでした。
何か、ヒントを思いつかれたら、お教えください。
よろしくお願いいたします。

何度もお手を煩わせて、申し訳ありませんでした。

回答No.3

c6h6

最短で全部運ぶ考え方としては、
「常に遅い船を1番早い船で曳航していき、復路を最短時間で帰る。」ということだと思います。
ということは、
3隻：4+1+2=7分
4隻：8+1+4+1+2=16分
5隻：16+1+8+1+4+1+2=33分
6隻：32+1+16+1+8+1+4+1+2=66分
7隻：64+1+32+1+16+1+8+1+4+1+2=131分

n隻あった場合の時間は、
往路は2+4+・・・+2^(n-1)
復路はn-2回×1分
ここで便宜上、復路の1回分を往路に足してしまって
往路＝1+2+4+・・・+1・2^(n-1)＝2^n-1
復路＝n-3
足し合わせると n>=3回の場合　2^n + n -4

とNo.1の方と同じ答えになりますが？

これ以外の最短ってありますかね？

例えば、
遅い船同士で運ぶとします。
n=4のとき
(8 and 4)を運ぶ　8分往路4分復路
(4 and 2)を運ぶ　4分往路2分復路
(2 and 1)を運ぶ　2分往路
計20分かかっちゃいます。

お礼

ご回答をありがとうございます。
ちょっと私の書き方が不十分で、申し訳ありません。
ご指摘のように、「帰りの船はどれでもかまわない」という条件が書いていませんでした。

回答No.2

fushigichan

uminezumiさん、こんばんは。
面白いクイズですね！！

＞（１）Ｓ5、Ｓ6は、これで合っているでしょうか？

n=1のとき、S1=1
n=2のとき、S2=2はいいと思います。

n=3のとき、行き1,2帰り１で３分
　　　　　行き１，４で４分なので合計７分。
　　　　　S3=7

n=4のとき、行き1,2帰り１で３分
　　　　　行き4,8帰り２で１０分　　
　　　　　行き１，２で２分なので、合計１５分
　　　　　S4=15

n=5のとき、行き1,2帰り１で３分
　　　　　　行き8,16帰り２で１８分
　　　　　残りのフネは、(1,2,4)なので
　　　　　S5=3+18+S3=28

n=6のとき、行き1,2帰り1で３分
　　　　　　行き16,32帰り２で３４分
　　　　　残りのフネは、(1,2,4,8)なので、
　　　　　S6=3+34+S4=52

となっているので、S5=28,S6=52というuminezumiさんの予想は合っていると思います。

＞（２）Ｓnを一般式で表すことができるでしょうか？

あらわすことはできるのでしょうか・・？？
フネの数が、偶数のときと奇数のときで場合わけしないといけないかも知れないですね。

S1=1
S2=2
S3=4+S1+S2
S4=13+S2
S5=21+S3
S6=37+S4
S7=69+S5
S8=133+S6
・・・と予想してみました。

(S8-S7)=64+(S6-S5)
(S7-S6)=32+(S5-S4)
(S6-S5)=16+(S4-S3)
(S5-S4)=8+(S3-S2)←ここまでは、数字のところは、2の何乗かになっているんですが・・
(S4-S3)=8
(S3-S2)=5
(S2-S1)=1

S[n+1]-S[n]=a[n]とおくと、
a1=1
a2=5
a3=8
a4=8+a2=13
a5=16+a3=24
a6=32+a4=45
a7=64+a5=88

う～ん・・・この数字に関連性はあるのかな・・
階差は考えないほうがいいみたいですね・・
ちょっと、ここまでしか分からないです。申し訳ないです。

お礼

こんばんは。
私の質問におつき合いくださいまして、ありがとうございます。

＞　となっているので、S5=28,S6=52というuminezumiさんの予想は合っていると思います。

私の考え方と同じでしたので、fushigichanさんにそう言ってもらえてホッとしています。

Ｓ1、Ｓ2、・・・、Ｓnを１つの数列と見て解こうとしましたが、私には難しすぎました。やはり、偶数、奇数で場合分けしたほうがよさそうですね。

＞　ちょっと、ここまでしか分からないです。申し訳ないです。

いえいえ、とんでもありません。解法の手がかりを、ありがとうございました。
ご回答に感謝しています。また何かわかりましたら、お教えいただければ幸いです。

回答No.1

he-goshite-

n = 1 （1）のとき　　　　　　　Ｓ1 = 1
n = 2 （1,2）のとき　　　　　　Ｓ2 = 2
n = 3 （1,2,4）のとき　　　　　Ｓ3 = 7
まではいいのですが，
n = 4 （1,2,4,8）のとき　　　　Ｓ4 = 16
ではないかしら？
順番に机上試行してみると，
Ｓ1 = 1
Ｓ2 = 2
Ｓ3 = 4 + 1 + 2
Ｓ4 = 8 + 1 + 4 + 1 + 2 ＝ ２^(4-1)＋1＋Ｓ3
同様に（ｎ≧3のとき）
Ｓn = ２^(n-1)＋1＋Ｓn-1　
となるのではないか，と思います。
これだと，　
Ｓ4 ＝16
Ｓ5 = 33
Ｓ6 = 66
となって，

一般式は，
n＝１のとき　Ｓn ＝１
n＝２のとき　Ｓn ＝２
n≧３のとき Ｓn ＝ ２^n ＋ｎ－4
ではないかしら

お礼

さっそくのご回答をありがとうございます。
私も最初は n = 4 のときは16かなと思ったのですが、
質問No.590136 にありますように、最短時間は15分 が正解のようです。
また何か新しいことがわかったら、教えていただけたら嬉しいです。