第345問の解答
問題[場合の数]
左図のような、1階と2階をつなぐ5段の階段(5段目は2階)があります。 この階段を1階にいるマサルさんが、1段ずつ、1段とばしの片方または両方を使って1往復します。
このとき、どの階段も、上りまたは下りの少なくともいずれか一方で踏むものとします。では、このような1往復の仕方は何通りあるでしょうか。
解答例1
辻。さん、まるケンさん、15KARATSOULさん、sugitakukunさん、トトロ@Nさん、ハリスさん、たけちゃんさん、がんばるさやかですさん、takaisaさん、kasamaさん、あほあほまんさん、●●●●●●さん、小西孝一さん、有無相生さん、M.Hossieさん、ミミズクはくず耳さん、ねこやんさん、幽玄太郎さん、abcdeさん、BossFさん、ふじさきたつみさん、mindsさん、フランク長いさん、Drkさん、東洋の計算機さん、他
1階から2階へ進むには、図1のように8パターンの場合があります。
ただし、各段について、数字の1=その段を踏む、0=踏まないを表します。次に上りの各パターンで場合分けします。
パターンA:
既に全ての段を踏んでいるので、下りはどのパターンでもOK・・・8通りパターンB:
上りで踏んでいない4段目を踏むA、C、D、F、H ・・・ 5通りパターンC:
上りで踏んでいない3段目を踏むA、B、D、E、F、G ・・・ 6通りパターンD:
上りで踏んでいない2段目を踏むA、B、C、F、G、H ・・・ 6通りパターンE:
上りで踏んでいない2、4段目を踏むA、C、F、H ・・・ 4通りパターンF:
上りで踏んでいない1段目を踏むA、B、C、D、E ・・・ 5通りパターンG:
上りで踏んでいない1、4段目を踏むA、C、D ・・・ 3通りパターンH:
上りで踏んでいない1、3段目を踏むA、B、D、E ・・・ 4通り従って、
合計=8+5+6+6+4+5+3+4=41通り
となります。答: 41通り
以上
解答例2
ICさん、CRYING DOLPHINさん、Toru Fukatsuさん、 他
2階までの段数がn段あるとして、場合の数をFnとし、nに関する漸化式を考えます。
まず、F1=1、F2=3は明らか。n≧3のとき、第1段、第2段の踏み方によって場合分けします。
ただし、以下では、A:上り・下りとも踏む、B:上りのみ踏む、C:下りのみ踏むと表します。(1)第1段を上り・下りとも踏むとき
第1段を1階と見なせば、残り(n-1)段について上り・下りのいずれかでは踏んでいることからFn-1通り
(2)第1段を上りのみ、第2段は両方とも踏むとき
第2段を1階と見なせば、残り(n-2)段について上り・下りのいずれかでは踏んでいることからFn-2通り
(3)第1段を上りのみ、第2段は下りのみ踏むとき
(4)第1段を下りのみ、第2段は両方踏むとき
(5)第1段を下りのみ、第2段は上りのみ踏むとき
(3)では、上りで1階から2段目に上るのを、1段目から上ることに置き換えて、
(4)、(5)では、上りで1階から2段目に上るのを、1段目から上ることに置き換えます。そして、それぞれ第1段を1階とみなせば、(4)は2段目を両方、(5)は上りのみ、(3)は下りのみ踏んでいるので、これらを合わせると、2段目およびそれ以降の合計(n-1)段について上り・下りのいずれかでは踏んでいることからFn-1通り
従って、(1)〜(5)より、Fn=2Fn-1+Fn-2が成り立つことが分かります。
よって、
n=3のとき、F3=2F2+F1=2×3+1=7通り
n=4のとき、F4=2F3+F2=2×7+3=17通り
n=5のとき、F5=2F4+F3=2×17+7=41通り
となり、本問では、F5=41通りとなります。
(その他の解法)
- プログラム(Jsva,Excelなど)で計算 ・・・ ちば けいすけさん、???さん、 他