「今月の問題」　第１０９回　（平成２０年１０月）

＜問題＞

　下図を見てください。
　よしお君の学校は、１１段からなる階段があります。よしお君は、１段あがりと２段あがりを用いて上がります。例えば下図のように３段の階段では３通り、４段の階段では５通りの上り方があります。

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

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

答えは１１４通りでした

　

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

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

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

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

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

いやはや、完敗です。

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

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

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

　
[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個の黒玉の並べ方と同様に考えられるので、
10C１＝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-1)段目から１歩上ったか、(n-2)段目から２歩上ったかどちらかだから

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