船のクイズの一般化

Question

先日、このサイトで面白いクイズを見つけたので（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を一般式で表すことができるでしょうか？

どうか、よろしくお願いいたします。

ryn · Accepted Answer

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) を同時に移動させるなどのような
方法でもっと短い時間で移動する方法があれば、
上の議論は無意味になってしまいますが…。

c6h6 · Answer

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) + ・・・ + のところを私には一般式にあらわすことができません。

ticky · Answer

こんばんは。
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
だと思います。

最速かどうかも分からないし、計算が合っているかどうか不安ですが。

TK0318 · Answer

ｎ＝２ｋ、２ｋ－１の時で場合分けします。

＊これは船が２隻増えた場合
・１，２で渡る
・１で帰る
・ａｎ、ａ（ｎー１）で渡る
・２で帰る
となりＳｎはＳｎ－２に比べてａｎ＋５分余計にかかります。

よって
Ｓ２ｋ＝Ｓ２（ｋ－１）＋ａ２ｋ＋５
Ｓ２ｋ－１＝Ｓ（２ｋ－３）＋ａ（２ｋ－１）＋５
ａ２ｋ＝２＊４＾（ｋ－１）
ａ２ｋ－１＝４＾（ｋ－１）
ａ１＝１
ａ２＝２
となります。

あとは等比数列ですが・・・私の実力では解けん＾＾；
多分これでいけると思います・・・

c6h6 · Answer

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

c6h6 · Answer

最短で全部運ぶ考え方としては、
「常に遅い船を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分かかっちゃいます。

fushigichan · Answer

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

he-goshite- · Answer

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 の場合からの類推で。

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

この回答への補足

こんばんは。

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

Oh! なるほどー

最短で全部運ぶ考え方としては、

uminezumiさん、こんばんは。

n = 1 （1）のとき Ｓ1 = 1

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

Oh!　なるほどー

n = 1 （1）のとき　　　　　　　Ｓ1 = 1