Laura’s pet bunny, Ghost, hops up a flight of 12 stairs. Ghost can hop up one or two steps at a time, and never hops down. How many ways can Ghost reach the top
number of cases, not worrying about order:
2hops 1 hop
6 0
5 2
4 4
3 6
2 8
1 10
0 12
number of ways each of the above can be arranged
e.g. the 5 double hops and 2 single hops could be
dddddss
sddddds
etc
6 0 --- 1
5 2 -- 7!/(5!2!) = 21
4 4 -- 8!/(4!4!) = 70
3 6 -- 9!/(3!6!) = 84
2 8 -- 10!/(2!8!) = 45
1 10 -- 11!/10!1! = 11
0 12 -- 1
different ways = sum of those = 233
To find out how many ways Ghost can reach the top of the stairs, we can use a dynamic programming approach. Let's define a function f(n) that represents the number of ways to reach the nth step.
To calculate f(n), we need to consider two cases:
1. If Ghost hops up one step, then Ghost has (n-1) steps remaining to reach the top. So, the number of ways to reach the top from this position is f(n-1).
2. If Ghost hops up two steps, then Ghost has (n-2) steps remaining to reach the top. So, the number of ways to reach the top from this position is f(n-2).
Therefore, the total number of ways to reach the top from the nth step is the sum of the number of ways to reach the top from (n-1)th step and (n-2)th step, i.e. f(n) = f(n-1) + f(n-2).
Using this recurrence relation, we can compute the number of ways to reach the top of the stairs for any given number of steps.
Let's calculate the number of ways for 12 steps using this approach:
1. f(1) = 1 (Ghost can directly hop up to the top)
2. f(2) = 2 (Ghost can either hop two steps at once or hop one step twice)
3. f(3) = f(2) + f(1) = 2 + 1 = 3 (Ghost can reach the third step by either hopping from the first or second step)
4. f(4) = f(3) + f(2) = 3 + 2 = 5
5. ...
6. f(12) = f(11) + f(10) = 89 + 55 = 144
Therefore, there are 144 different ways for Ghost to reach the top of the 12 stairs.