「今月の問題」 第109回 (平成20年10月)

<問題>

 下図を見てください。
 よしお君の学校は、11段からなる階段があります。よしお君は、1段あがりと2段あがりを用いて上がります。例えば下図のように3段の階段では3通り、4段の階段では5通りの上り方があります。

 ここで問題です。よしお君は、11段の階段の上り方を最大何通り見つけることができるでしょうか。(ヒント、答えは3の倍数になりそうです)


<正解者一覧表>           
正解者順位     name      メール到着日時     備 考  
 1ルルゥ さん2008/10/1 0:05 
 2algebra さん2008/10/1 0:06神奈川県 
 3Mr.ダンディ さん2008/10/1 0:11大阪府 
 4ラスカマン さん2008/10/1 0:42静岡県伊豆半島 
 5ゴンとも さん2008/10/1 0:51 
 6ma-mu-ta さん2008/10/1 0:57東京都 
 7浪人 さん2008/10/1 1:22岩手県大船渡市 
 8いちもく さん2008/10/1 4:41立川市 
 9巷の夢 さん2008/10/1 6:52宮城県出身 
10NAMPOTのPOT さん2008/10/1 7:44 
11teki さん2008/10/1 9:41大阪府 
12fisherman さん2008/10/1 10:54豊岡市・塾講師
13元気モリモリ さん2008/10/1 11:12宮崎 
14nak さん2008/10/1 12:12鹿児島県 
15やぶコウノトリ さん2008/10/1 17:09 
16スモークマン さん2008/10/1 19:21ジタンも結構美味い^^v 
17魔法使いサリン さん2008/10/1 21:10滋賀県 
18経友会の進作 さん2008/10/1 21:48京都府木津川市・70歳
19りーくん さん2008/10/1 23:46埼玉県 
20Daigorow さん2008/10/2 0:15埼玉県 
21こしひかり さん2008/10/2 0:21おおさか 
22マッキー27 さん2008/10/2 1:10愛知県 
23oguchan1 さん2008/10/2 1:14 
24uchinyan さん2008/10/2 14:24東京都 
25SaiSai さん2008/10/2 16:06大阪市・走るプログラマ
26igyora さん2008/10/2 17:38 
27川村高雅 さん2008/10/2 17:53神奈川県 
28鞍馬の天狗 さん2008/10/2 21:10大阪府中二 
29 まいすた さん2008/10/2 22:36 
30宮 さん2008/10/3 0:53鹿児島県放送大学学生 
31川村高雅 さん2008/10/3 4:27神奈川県 
32タカピー さん2008/10/3 18:51中学生 
33なにわ さん2008/10/4 19:50西宮市 
34川上智弘 さん2008/10/5 17:39兵庫県 
35kasama さん2008/10/5 20:47和歌山県プログラマ 
36 ゆうり さん2008/10/5 21:16作曲家 
37男はつらいよ さん2008/10/6 10:37横浜市 
38ぴーしゅん さん2008/10/6 13:11 
39tomo2 さん2008/10/7 13:50東京都 
40理科ちゃんマン さん2008/10/7 15:34理科の塾講師@兵庫県
41muffin さん2008/10/8 16:47 
42とおりすがりのミズ さん2008/10/9 20:16京都 
43中3(復活)!?航空アニマル さん2008/10/9 22:06東京都26市内中学3年生
44信三 さん2008/10/10 3:01金門公園の隠居 
45かず さん2008/10/10 15:18熊本 
46 banyanyan さん2008/10/10 15:32京都府
47安楽 さん2008/10/10 23:14宮崎県 
48akira さん2008/10/11 8:31東京都 
49today さん2008/10/14 5:48 
50桜井杏 さん2008/10/15 6:21東京都 
51いがぐり次郎 さん2008/10/16 22:01 
52サバトラ さん2008/10/17 12:07福岡 
53黒アイス さん2008/10/17 22:39日本のどこか 
54新俳人澄朝 さん2008/10/18 11:05津山市 
55算算サン さん2008/10/19 17:07滋賀っ県 
56 ioioio さん2008/10/19 17:15 
57hassy さん2008/10/19 18:43さいたま 
58す さん2008/10/21 12:57城崎 
59矢田川の鯉 さん2008/10/21 22:46会社員 
60 阿修羅 さん2008/10/22 15:14長野県小学校教諭
61ヌルハチ さん2008/10/24 21:58山形県出身です
62horitama さん2008/10/28 15:48富山県と石川県の県境
63ruto11 さん2008/10/29 19:07 
64〜おぐじ〜 さん2008/10/31 0:39京女小京都育ちでーす

答えは114通りでした

 

[121] フィボナッチ数列でしたね 投稿者:安楽 投稿日:2008/10/10(Fri) 23:21 [返信]

こういった問題は難しく考えずに7段くらいまで実行すれば良い。組み合わせもあるんですね。

 
[120] フィボナッチ数列でしたか。 投稿者:ゆうり 投稿日:2008/10/05(Sun) 21:21 [返信]

私も2回上がりの回数で場合分けをし、
順列を使って解きました。

もっと簡単な方法があるのではと思ったのですが、
漸化式には気付きませんでしたね。

いやはや、完敗です。

 
[119] Re:[117] 本当にこれでいいのですか? 投稿者:Mr.ダンディ 投稿日:2008/10/05(Sun) 15:16 [返信]

> 2段上がりの回数で場合分けをし,反復試行の考え?でそぜぞれの場合の数を計算し,その和が答えとなる。
>
> というわけです。本当にこれでいいのか?

理にかなっており正しいと思います。立派な1解法ですね。

 
[118] フィボナッチ数列 投稿者: 投稿日:2008/10/03(Fri) 00:51 [返信]

この問題はフィボナッチ数列になっていて、前の2項を足したものが、答えになっています。以下のようになりました。
1,1,2,3,5,8,13,21,34,55,89,144


 
[117] 本当にこれでいいのですか? 投稿者:fisherman 投稿日:2008/10/02(Thu) 23:20 [返信]

もしかして答えが合ったのは偶然なのか?考え方は以下の通りです。

2段上がりの回数で場合分けをし,反復試行の考え?でそぜぞれの場合の数を計算し,その和が答えとなる。

0回の場合はすべて1段上がりなので1通り。
 
1回の場合は2段をセットにして1段と考えると,全部で10段となります。10段のうち2段上がりは何段目でもいいわけですから,10C1。
 
2回の場合は2段セットが2組なので,ぜんぶで9段となりす。同様に9C2。

同様に3回,4回,5回の場合を計算する。

そして和を求める。

というわけです。本当にこれでいいのか?

 
[116] っていうか・・・ 投稿者:三日月キリン 投稿日:2008/10/02(Thu) 21:27 [返信]

フィボナッチ数列って有名なんですね・・・
聞いたことも無いです(−−ム)

今は中学生くらいで習うんですか?

 
[115] ふぅ〜 投稿者:三日月キリン 投稿日:2008/10/02(Thu) 21:23 [返信]

組み合わせで解きました。
fishermanさんと考え方は同じかな?
以下回答です。

-------------------------------------
1歩と2歩の組み合わせによって、11歩になるようなものを考える。

まず全て1歩で登る登り方は1通り。

次に、一度だけ2歩歩く歩き方を考える。
一度だけ2歩歩く組み合わせを入れるので、
合計すると11歩になるようにするためには、
1歩を9回、2歩を1回にすればいい。
これは、9個の白玉と1個の黒玉の並べ方と同様に考えられるので、
10C1=10通り

今度は、2歩を2回に増やすと、
1歩を7回、2歩を2回の組み合わせで11歩になる。
今度は、7個の白玉と2個の黒玉の並べ方と同様に考えられるので、
9C2=36

以下、2歩が3回・4回・5回と同様に考えると、
それぞれ56・35・6通りである。

これらを合計すると、144通り。

よって回答は144通りとなる。 (以上
--------------------------------------------

こんな感じです。


基礎丸暗記だと出来ないけど、きちんと理解している子は解けそうな、
章末問題みたいな感じですね。

 
[114] 有名な問題ですね 投稿者:鞍馬の天狗 投稿日:2008/10/02(Thu) 21:12 [返信]

恐らく
F(n+2)=F(n+1)+F(n)だと思います…
フィボナッチですね



 
[113] Re:[111] これでいいのか? 投稿者:スモークマン 投稿日:2008/10/02(Thu) 02:54 [返信]

> 直感ですが,
> 11C11+10C1+9C2+8C3+7C4+6C5=144
> となりました。

これはどんな考え方をされたのか教えていただければうれしいです m(_ _)mv

ちなみに、わたしも漸化式・・・フィボナッチ数列になるわけですが・・・で解く方法を知ってました♪


 
[112] 早く解けました。 投稿者:とし 投稿日:2008/10/01(Wed) 15:34 [返信]

フィボナッチ数列になりますね。

 
 
[111] これでいいのか? 投稿者:fisherman 投稿日:2008/10/01(Wed) 10:53 [返信]

直感ですが,
11C11+10C1+9C2+8C3+7C4+6C5=144
となりました。


 
[110] これと似た問題として 投稿者:ゴンとも 投稿日:2008/10/01(Wed) 04:32 [返信]

8月9日の算チャレv3でバスケットの点数の問題で
計10点で1,2,3点の3タイプある問題で
カキコした解法は以下のようなものでした。

一段上り,二段上りの回数をそれぞれa,bとすると
a+2*b=11 これを満たすものは以下でその横はその並び替えでできる通り数
a=1,b=5 6!/(5!)=6通り
a=3,b=4 7!/(3!*4!)=35通り
a=5,b=3 8!/(5!*3!)=56通り
a=7,b=2 9!/(7!*2!)=36通り
a=9,b=1 10!/9!=10通り
a=11,b=0 1通り
この総計で
6+35+56+36+10+1=144通り・・・・・・(答え)

 
[109] フィボナッチ数列 投稿者:ゴンとも 投稿日:2008/10/01(Wed) 00:50 [返信]

とすぐわかりましたが寝過ごしました。

 
[108] フィボナッチ数列 投稿者:Mr.ダンディ 投稿日:2008/10/01(Wed) 00:26 [返信]

n段目にいたる直前は (n-1)段目から1歩上ったか、(n-2)段目から2歩上ったかどちらかだから

n段を上るときの場合の数をa[n]通りとすると
a[n]=a[n-1]+a[n-2]
が成り立ち、かの有名なフィボナッチ数列となる。
・・・と気づかせる問題設定ですね・・・