場合の数と確率の問題

各段に着くまでののぼり方の数を、下の段から順に表にまとめる。

$n$ 段目に着く直前には、$n-1$ 段目から $1$ 段のぼるか、$n-2$ 段目から $2$ 段のぼるかのどちらかである。よって、$n$ 段目に着くのぼり方の数は、$(n-1)$ 段目に着くのぼり方の数と $(n-2)$ 段目に着くのぼり方の数の和になる。ただし、こわれている段に着くのぼり方は $0$ 通りとする。

• $0$ 段目: $1$ 通り（出発点）
• $1$ 段目: $1$ 通り
• $2$ 段目: $1+1=2$ 通り
• $3$ 段目: $2+1=3$ 通り
• $4$ 段目: $3+2=5$ 通り
• $5$ 段目: こわれているので $0$ 通り
• $6$ 段目: $0+5=5$ 通り（$4$ 段目から $2$ 段のぼるしかない）
• $7$ 段目: $5+0=5$ 通り
• $8$ 段目: $5+5=10$ 通り
• $9$ 段目: こわれているので $0$ 通り
• $10$ 段目: $0+10=10$ 通り（$8$ 段目から $2$ 段のぼるしかない）
• $11$ 段目: $10+0=10$ 通り
• $12$ 段目: $10+10=20$ 通り

したがって、のぼり方は全部で $20$ 通りである。

（確かめ）$5$ 段目に足をつけないので、必ず $4$ 段目から $6$ 段目へ $2$ 段のぼる。$9$ 段目に足をつけないので、必ず $8$ 段目から $10$ 段目へ $2$ 段のぼる。$0$ 段目から $4$ 段目までが $5$ 通り、$6$ 段目から $8$ 段目までが「$1$ 段, $1$ 段」「$2$ 段」の $2$ 通り、$10$ 段目から $12$ 段目までも $2$ 通りなので、$5\times 2\times 2=20$ 通りとなり、一致する。

$n$ 段目に着くのぼり方の数を $f(n)$ とする。$n$ 段目には $n-1$ 段目か $n-2$ 段目から来るので、こわれていない段では $f(n)=f(n-1)+f(n-2)$。こわれている段では $f(n)=0$。
$f(0)=1$、$f(1)=1$、$f(2)=2$、$f(3)=3$、$f(4)=5$。
$f(5)=0$（こわれている）。
$f(6)=f(5)+f(4)=0+5=5$、$f(7)=f(6)+f(5)=5$、$f(8)=f(7)+f(6)=10$。
$f(9)=0$（こわれている）。
$f(10)=f(9)+f(8)=10$、$f(11)=f(10)+f(9)=10$、$f(12)=f(11)+f(10)=20$。
検算: 必ず $4$ 段目、$6$ 段目と $8$ 段目、$10$ 段目を通る。$0\to 4$ は $5$ 通り、$4\to 6$ は $1$ 通り、$6\to 8$ は $2$ 通り（$5$ を通らないので $6\to 7\to 8$ と $6\to 8$）…ではなく、$6\to 8$ は $2$ 通り、$8\to 10$ は $1$ 通り、$10\to 12$ は $2$ 通りと考えると、$4\to 6$ は直接 $2$ 段で $1$ 通り、$4\to 8$ は $6$ を通る $4\to 6\to 7\to 8$、$4\to 6\to 8$ の $2$ 通り、$8\to 12$ は $10$ を通る必要があり $8\to 10\to 11\to 12$、$8\to 10\to 12$ の $2$ 通りなので $5\times 2\times 2=20$ となり一致する。