2010 AMC 8 Problems/Problem 25
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?
We will systematically consider all of the possibilities. A valid climb can be thought of as a sequence of some or all of the numbers , , and , in which the sum of the sequence adds to . Since there is only one way to create a sequence which contains all , all , or all , there are three possible sequences which only contain one number. If we attempt to create sequences which contain one and the rest , the sequence will contain one and four . We can place the in either the first, second, third, fourth, or fifth position, giving a total of five possibilities. If we attempt to create sequences which contain one and the rest , the sequence will contain one and three . We can place the in either the first, second, third, or fourth position, giving a total of four possibilities. For sequences which contain exactly two and the rest , the sequence will contain two and two . The two could be next to each other, separated by one in between, or separated by two in between. We can place the two next to each other in three ways, separated by one in two ways, and separated by two in only one way. This gives us a total of six ways to create a sequence which contains two and two . Note that we cannot have a sequence of only and since the sum will either be or greater than . We now only need to consider the case where we use all three numbers in the sequence. Since all three numbers add to , the number of permutations of the three numbers is . Adding up the number of sequences above, we get: . Thus, answer choice is correct.
A recursive 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
Complementary counting is also possible. Considering the six steps, Jo has to land on the last step, so there are ways to land on 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. -adyj
|2010 AMC 8 (Problems • Answer Key • Resources)|
|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|