2010 AMC 8 Problems/Problem 25
Contents
Problem
Everyday at school, Jo climbs a flight of stairs. Jo can take the stairs , , or at a time. For example, Jo could climb , then , then . In how many ways can Jo climb the stairs?
Solution 1
A dynamics programming approach is quick and easy. The number of ways to climb one stair is . There are ways to climb two stairs: , or . For 3 stairs, there are ways: (,,) (,) (,) ()
For four stairs, consider what step they came from to land on the fourth stair. They could have hopped straight from the 1st, done a double from #2, or used a single step from #3. The ways to get to each of these steps are ways to get to step 4. The pattern can then be extended: steps: ways. steps: ways. steps: ways.
Thus, there are ways to get to step
Solution 2
Complementary counting is also possible. Considering the six steps, Jo has to land on the last step, so there are subsets (hit steps) of the other five steps. After that, subtract the number of ways to climb the steps while taking a leap of , , or . The eight possible ways for this is (, , ), (, ), (, , ), (, , ), (, ), (, ), (, ), and ()
Altogether this makes for valid ways for Jo to get to step 6.
Solution 3 (Recursion)
We can set up a recursion to solve this problem. Suppose represents the number of valid ways to get to the th step. because there is 1 way for Jo to get to the "th" step (i.e. the ground). There is way to get to the first step (a -step), so . There are ways to get to the second step (two -steps or one -step). Thus, . In general, . This is because from the th step, Jo can take a -step to get to the th step, from the th step, Jo can take a -step to get to the th step, and from the th step, Jo can take a -step to get to the th step. We now iteratively calculate values of .
~ cxsmi
Video Solution by OmegaLearn
https://youtu.be/5UojVH4Cqqs?t=4560
~ pi_is_3.14
Video by MathTalks
See Also
2010 AMC 8 (Problems • Answer Key • Resources) | ||
Preceded by Problem 24 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
All AJHSME/AMC 8 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.