2010 AMC 8 Problems/Problem 25
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
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.
Solution 2
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
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.
Extra Stuff
Check out Numberphile's Youtube Channel!
NOOOOOOOOOO!
6523879mfgntihglsdhsd foiajmdsn vcufckgjmdoifhvgfdynbtijgggggknsdjklbNDFJ89htiuos n LOLOLI get reckt