![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?8acaa2e)
先日、このサイトで面白いクイズを見つけたので(590136)、問題を一般化してみました。
------------------------------------------------------
船がn艘あり、これを船頭さんが一人で対岸まで移動します。
n艘の船は川を横切るのにそれぞれ1分、2分、4分、、、2^(n-1)分かかります。
船頭さんは1艘を運転し、もう1艘をその船に牽引することができます。
ただし、2艘を同時に移動する場合、そのスピードは遅い方の船のスピードになります。
また、船で元の岸に帰ってくる時間も考えなければなりません。
船を全て向こう岸まで移動するのに必要な最短時間Sn(分)を求めてください。
------------------------------------------------------
nを1から考えてみると、
n = 1 (1)のとき S1 = 1
n = 2 (1,2)のとき S2 = 2
n = 3 (1,2,4)のとき S3 = 7
n = 4 (1,2,4,8)のとき S4 = 15
n = 5 (1,2,4,8,16)のとき S5 = 28
n = 6 (1,2,4,8,16,32)のとき S6 = 52
・
・
そこでお聞きしたいのですが、
(1)S5、S6は、これで合っているでしょうか?
(2)Snを一般式で表すことができるでしょうか?
どうか、よろしくお願いいたします。
No.7ベストアンサー
- 回答日時:
n = 4 の場合からの類推で。
時間のかかる船2隻で一緒に移動するという方針で考えてみます。
1番遅い船にまぎれて2番目に遅い船を移動させたのに
そのどちらかで戻ってきては意味がありません。
したがって、先に1分、2分かかる船で移動しておきます。
具体的には
往路 復路
1-2 1(or 2)
2^(n-2)-2^(n-1) 2(or 1)
1-2 -
で遅い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 が3以上の奇数のときは
S_n = (2/3)*2^n + (5/2)n - 35/6
となります。
最初の前提を証明できていないので、
2^(n-1) と 2^(n-3) を同時に移動させるなどのような
方法でもっと短い時間で移動する方法があれば、
上の議論は無意味になってしまいますが…。
こんばんは。
とても分かりやすくて、スッキリしたご回答をありがとうございました。最短時間を求めるアルゴリズムは、これ以外には私には想像もつきませんが、もっと画期的な方法があるのでしょうか?
ともあれ、このような明解な回答をいただいて、非常に満足しています。
本当にありがとうございました。
No.8
- 回答日時:
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) + ・・・ + のところを私には一般式にあらわすことができません。
この回答への補足
みなさま、たくさんのご回答をありがとうございました。数学カテゴリーは、その他(ライフ)に次いで私の好きなカテゴリーですが、いつも明解な回答を目にして、みなさまの頭脳にただただ尊敬の念を抱いています。私の悩みも解決しましたので、これで閉めさせていただきたいと思います。
たくさんの回答をいただいて、ポイントをおつけするのは、いつも悩むのですが、非常にわかりやすく説いてくださったrynさまに20ポイント、まっ先にS5、S6を検算し、偶数、奇数の場合分けが必要と予測してくださったfushigichanさまに10ポイントをつけさせていただきましたが、ほかの方々にもポイントをおつけしたい気持ちでいっぱいです。
みなさま、大変ありがとうございました。またいつか、しょーもない質問をすると思いますが、どうぞよろしくお願いいたします。
ベンゼンさま、いや違いました、c6h6さま、再度のご回答をありがとうございます。
最初にご回答をいただいてから、あっという間にたくさんのご回答をいただき、やっと私の頭でも理解できました。解法のやり方としては、おっしゃられている通りだと思います。楽しい数時間でした。大変ありがとうございました。
No.6
- 回答日時:
こんばんは。
n>=4において、
S_n=5+2^(n-1)+S_(n-2)
が成立しているようです。
この式は、始めに1分かかる船と2分かかる船で行って、1で戻ってきて、一番遅い船と次に遅い船で行って、
2分かかる船で戻ってくると、
後は、1分かかる船から2^(n-2)分かかる船までが残っている・・・という方法を採用した場合です。
これに基づくと、
S_1=1
n>=1で、
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
- 回答日時:
n=2k、2k-1の時で場合分けします。
*これは船が2隻増えた場合
・1,2で渡る
・1で帰る
・an、a(nー1)で渡る
・2で帰る
となりSnはSn-2に比べてan+5分余計にかかります。
よって
S2k=S2(k-1)+a2k+5
S2k-1=S(2k-3)+a(2k-1)+5
a2k=2*4^(k-1)
a2k-1=4^(k-1)
a1=1
a2=2
となります。
あとは等比数列ですが・・・私の実力では解けん^^;
多分これでいけると思います・・・
こんばんは。いつもお世話になります。
考え方は分かりやすくて、私にも理解できました。
> あとは等比数列ですが・・・私の実力では解けん^^;
またまたご冗談を。TK0318さんの実力からして、「解けるけど、面倒くさいから、自分で解いてね」というメッセージだと理解しました。☆^^☆
ご回答をありがとうございました。
No.3
- 回答日時:
最短で全部運ぶ考え方としては、
「常に遅い船を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
- 回答日時:
uminezumiさん、こんばんは。
面白いクイズですね!!
>(1)S5、S6は、これで合っているでしょうか?
n=1のとき、S1=1
n=2のとき、S2=2はいいと思います。
n=3のとき、行き1,2帰り1で3分
行き1,4で4分なので合計7分。
S3=7
n=4のとき、行き1,2帰り1で3分
行き4,8帰り2で10分
行き1,2で2分なので、合計15分
S4=15
n=5のとき、行き1,2帰り1で3分
行き8,16帰り2で18分
残りのフネは、(1,2,4)なので
S5=3+18+S3=28
n=6のとき、行き1,2帰り1で3分
行き16,32帰り2で34分
残りのフネは、(1,2,4,8)なので、
S6=3+34+S4=52
となっているので、S5=28,S6=52というuminezumiさんの予想は合っていると思います。
>(2)Snを一般式で表すことができるでしょうか?
あらわすことはできるのでしょうか・・??
フネの数が、偶数のときと奇数のときで場合わけしないといけないかも知れないですね。
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さんにそう言ってもらえてホッとしています。
S1、S2、・・・、Snを1つの数列と見て解こうとしましたが、私には難しすぎました。やはり、偶数、奇数で場合分けしたほうがよさそうですね。
> ちょっと、ここまでしか分からないです。申し訳ないです。
いえいえ、とんでもありません。解法の手がかりを、ありがとうございました。
ご回答に感謝しています。また何かわかりましたら、お教えいただければ幸いです。
No.1
- 回答日時:
n = 1 (1)のとき S1 = 1
n = 2 (1,2)のとき S2 = 2
n = 3 (1,2,4)のとき S3 = 7
まではいいのですが,
n = 4 (1,2,4,8)のとき S4 = 16
ではないかしら?
順番に机上試行してみると,
S1 = 1
S2 = 2
S3 = 4 + 1 + 2
S4 = 8 + 1 + 4 + 1 + 2 = 2^(4-1)+1+S3
同様に(n≧3のとき)
Sn = 2^(n-1)+1+Sn-1
となるのではないか,と思います。
これだと,
S4 =16
S5 = 33
S6 = 66
となって,
一般式は,
n=1のとき Sn =1
n=2のとき Sn =2
n≧3のとき Sn = 2^n +n-4
ではないかしら
さっそくのご回答をありがとうございます。
私も最初は n = 4 のときは16かなと思ったのですが、
質問No.590136 にありますように、最短時間は15分 が正解のようです。
また何か新しいことがわかったら、教えていただけたら嬉しいです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 政治 魔改造した知床観光船に何十人も載せれる自民党の作った現在の法律がダメですよね? 4 2022/05/30 12:12
- 物理学 ここで回答している相対論信者って全員、相対性理論を理解できてないですよね? 4 2023/03/08 12:40
- 政治 知床半島の沖合で遭難した観光船ですが、日本は訴訟が少ない事と関係あるのではないでしょうか? 1 2022/04/25 22:06
- 船舶・クルーズ 帆船が港から出港する際の移動原理は? よく狭い隙間に停泊している帆船の描写があるじゃないですか。毎回 3 2022/06/17 18:31
- 船舶・クルーズ 中古艇ドットコムで探していた形と値段の船を見つけたので電話をして船の購入を考えているので現物を見たい 1 2022/12/14 20:29
- 哲学 この物語で一番悪いのは誰か?ランキング。 8 2023/04/22 12:35
- 物理学 ループしている世界で光の思考実験。 3 2023/02/05 07:35
- 日本語 ♪ 船の船頭で 暮らそうよ ♪、意味としては”船頭”だけで十分なところに、”船の”を付け加えるの 9 2023/08/13 11:25
- 船舶・クルーズ 潜水艦で世界一周旅行あれば行ってみたいですか? 旅行期間は1年間、横浜から出発した潜水艦は一気に海底 6 2023/03/26 11:48
- 電車・路線・地下鉄 「伊豆急リゾート21」について。8000系や3000系との使い分けは? 黒い外観が黒船電車ですか? 1 2022/11/15 13:01
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報