Difference between revisions of "2010 AMC 8 Problems/Problem 25"
(→Solution 3) |
(→Problem) |
||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | Everyday at school, | + | Everyday at school, Jomama climbs a flight of <math>6</math> stairs. Jo can take the stairs <math>1</math>, <math>2</math>, or <math>3</math> at a time. For example, Jomam could climb <math>3</math>, then <math>1</math>, then <math>2</math>. In how many ways can Jomam climb the stairs? |
<math> \textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24 </math> | <math> \textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24 </math> |
Revision as of 20:29, 30 December 2023
Contents
[hide]Problem
Everyday at school, Jomama climbs a flight of stairs. Jo can take the stairs
,
, or
at a time. For example, Jomam could climb
, then
, then
. In how many ways can Jomam climb the stairs?
Solution 1
A valid climb is a sequence of some or all of the ,
, and
step hops, in which the sum of the sequence adds to
.
There are three possible sequences which only contain one number- all the , all
, or all
.
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.
- Note that this strategy is impractical (and error-prone) for larger numbers.
Solution 2
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 3
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.
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.