2010 AMC 8 Problems/Problem 25

Problem

Everyday at school, Jo climbs a flight of $6$ stairs. Jo can take the stairs $1$ , $2$ , or $3$ at a time. For example, Jo could climb $3$ , then $1$ , then $2$ . In how many ways can Jo climb the stairs?

$\textbf{(A)}\ 13 \qquad\textbf{(B)}\ 18\qquad\textbf{(C)}\ 20\qquad\textbf{(D)}\ 22\qquad\textbf{(E)}\ 24$

Solution 1

A dynamics programming approach is quick and easy. The number of ways to climb one stair is $1$ . There are $2$ ways to climb two stairs: $1$ , $1$ or $2$ . For 3 stairs, there are $4$ ways: ( $1$ , $1$ , $1$ ) ( $1$ , $2$ ) ( $2$ , $1$ ) ( $3$ )

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 $1+2+4=7$ ways to get to step 4. The pattern can then be extended: $4$ steps: $1+2+4=7$ ways. $5$ steps: $2+4+7=13$ ways. $6$ steps: $4+7+13=24$ ways.

Thus, there are $\boxed{\textbf{(E) } 24}$ ways to get to step $6.$

Solution 2

Complementary counting is also possible. Considering the six steps, Jo has to land on the last step, so there are $2^5=32$ subsets (hit steps) of the other five steps. After that, subtract the number of ways to climb the steps while taking a leap of $4$ , $5$ , or $6$ . The eight possible ways for this is ( $4$ , $1$ , $1$ ), ( $4$ , $2$ ), ( $1$ , $4$ , $1$ ), ( $1$ , $1$ , $4$ ), ( $2$ , $4$ ), ( $1$ , $5$ ), ( $5$ , $1$ ), and ( $6$ )

Altogether this makes for $32-8= \boxed{\textbf{(E) 24}}$ 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

https://youtu.be/mSCQzmfdX-g

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

Page

Toolbox

Search