小学6 算数の問題です。

何通りありますか?という類です。

蛙が川を飛び越えます。川には葉っぱがあり、それにジャンプしたり、飛び越えたりします。
例えば、葉っぱが3枚あった場合
左から1,2,3、ジャンプしたら J とします。
123
12j
1j3
j23
j2j
の5通りです。2つの葉っぱは飛び越えられません。

質問
1、葉っぱが8枚のとき、蛙の渡り方は何通り?
2、葉っぱが20枚のときは?

よろしくお願いします。

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2015/02/24 12:04:45
  • 終了:2015/03/03 12:05:04

回答(3件)

id:MIYADO No.1

みやど回答回数340ベストアンサー獲得回数732015/02/24 13:03:53

フィボナッチ数列じゃないですか。小学校の問題じゃないでしょ。

と思ったら、「ネタ・ジョーク」でしたね。


とはいえ、ネタにマジレス。

詳しくは、n枚の場合にa(n)通り(普通は(n)と書かずに添字にする)とすると、

n(≧2)のときは、最後の葉っぱに着地する場合とジャンプする場合があり、前者については最初の(n-1)枚を着地するかジャンプするかを考えればよいのでa(n-1)通りで、後者の場合はその1つ前の葉っぱに着地せざるを得ないので、残りの(n-2)枚について考えればいいのでa(n-2)通りとなり、合わせると
a(n)=a(n-1)+a(n-2)

なおa(0)はまっすぐ飛び越えるだけなのでa(0)=1
a(1)は1枚の葉っぱに着地すると飛び越えるかなのでa(1)=2


以上より、n=0から順次
1, 2, 3, 5 (n=3), 8, 13, 21, 34, 55 (n=8), …, 17711 (n=20), …
となる。

強いてnの式で書くなら
φ=(1+√5)/2
として
a(n)={φ^(n+1)-(-φ)^(-n-1)}/√5
となる。

id:NAPORIN No.2

なぽりん回答回数4644ベストアンサー獲得回数8512015/02/24 13:28:00

ジャンプというのをjとしていますが、パス(上を飛び越える)意味でpのほうがわかりやすいですね。
ついでに、葉っぱは一列に並んでおり、戻ることはない(ルートは1本しかない)ようですね。
12323232というような進み方はしないわけだ。

それなら、葉っぱに、1、2とそれぞれ名前をつけずとも、着地のtですみます。
3枚の葉っぱ問題は
ttt (着地・着地・着地)
ptt (とびこえ・着地・着地)
tpt
ttp
ptp
の5通りに書き換えられます。
 
 
これを8枚にしたなら、

tttttttt このタイプをpゼロ個ルートと名付けます
pttttttt このタイプのをp1個ルートとなづけ、8種類あります。
ptpttttt このタイプのをp2個ルートとなづけます。
 
というようにpの数が4になるまでいちいちかぞえてみましょう。
pが5になるとどこかでpが二つ並んで連続飛び越えになるのでアウトです。

p2個ルートの場合は、28通り(高校生なら8c2といえばわかる)
このうちpが2回連続になる場合は7通り あるのでさしひいて21通り
そういった形で簡略化できます。
 
pが3個になったら、全とおりのとびこえから、p2個連続と、p3個連続を差し引きます。
 

pが2個いじょうあるルートの簡単な計算方法をみつけたら、あとはいくつ増えてもおなじことです。
8枚なら時間は少々かかりますがコンピューターでやるほど難しくはありません。
小学生が大きな紙にかきこみながらやれば15分くらいで出来ます。
20枚なら確率統計(cというのはコンビネーション)を習った高校生ならわりと速くできます。
小学生にはよほどがんばりのある子でないと、20枚は無理かもしれません。答えはざっと考えても200ルートを越えます。4000枚以上のはっぱ(pやt)を全部まちがえずに描くのは大変ですからね。

他9件のコメントを見る
id:MIYADO

自分の回答でもこちらに通知が来ますが何か。
リンク先のも自分の回答にコメントをつけるという想定ですが何か。

2015/02/24 19:36:18
id:NAPORIN

そして私にも質問者にも通知がいって、倍速で迷惑値が増していくので、明日には公式から何らかの対処が予測されるにせよ、もうこれ以上ここにかきこまないでください。一晩中迷惑を拡大する行為をなさるつもりですか。ご自分の感想はご自分のチラシの裏へどうぞ。

2015/02/24 19:40:15
id:a-kuma3 No.3

a-kuma3回答回数4439ベストアンサー獲得回数18232015/02/24 14:28:21

途中まで来て、次の葉っぱに移るときを考えます。

今、葉っぱを踏んでいるのであれば、次の葉っぱは、飛び越えても、踏んでも良い。
なので、今、葉っぱを踏んでいる状態になる組み合わせの数を No としたら、次に進む組み合わせは、No×2 通りあります。

今、葉っぱを飛び越えているのであれば、次の葉っぱは、踏むしかない。
そこまでの組み合わせの数を Nj としたら、次に進む組み合わせは、Nj 通りです。

ここまでの組み合わせは、今踏んでるか、飛び越えているかの合計で、No+Nj です。
次の葉っぱまで行く、つまり、もう一枚増えた場合には、2 No + Nj 通りです。

これを、表に整理してみます。
f:id:a-kuma3:20150224142700p:image


漸化式という言葉は使っていませんが、考え方を理解、もしくは思いつくことができないと厳しい感じですね。




肝心の答えを書くのを忘れてました (^^;

葉っぱの枚数最後に
葉っぱを踏む
組み合わせの
数 (A)
最後に
葉っぱを飛び越す
組み合わせの
数 (B)
組み合わせの
数 (A+B)
1
1
1
2
2
2
1
3
3
3
2
5
4
5
3
8
5
8
5
13
6
13
8
21
7
21
13
34
8
34
21
55
9
55
34
89
10
89
55
144
11
144
89
233
12
233
144
377
13
377
233
610
14
610
377
987
15
987
610
1597
16
1597
987
2584
17
2584
1597
4181
18
4181
2584
6765
19
6765
4181
10946
20
10946
6765
17711



足し算しか使ってませんから、筆算でも2分くらいあれば、n=20 も解けそうです。
別の回答にある「解がフィボナッチ数列だ」ということに気が付けば、もっと簡単に計算できますが、小学生でフィボナッチ数列を知っているのは稀だろう、ということで表を埋める形で計算します。
# 実際にやってみて、計算間違いをしたのは内緒だ

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません