Problem:
A cat is going up a stairwell with ten stairs. However, instead of walking up the stairs one at a time, the cat jumps, going either two or three stairs up at each step (though if necessary, it will just walk the last step). How many different ways can the cat go from the bottom to the top?
Solution
Solution:
The number of ways for the cat to get to the th step is the number of ways for the cat to get to step plus the number of ways to get to step , because for each way to get to step , we can undo the last move the cat made to go back to one of these two steps. The cat can get to step in ways, to step in way, and to step in way. Now we repeatedly use our formula for calculating the number of ways to get to the th step to see that the cat gets to:
| Step | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Number of ways | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 |
So our answer is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.