# Difference between revisions of "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 valid climb is a sequence of some or all of the $1$, $2$, and $3$ step hops, in which the sum of the sequence adds to $6$. There are three possible sequences which only contain one number- all the $1s$, all $2s$, or all $3s$. If we attempt to create sequences which contain one $2$ and the rest $1s$, the sequence will contain one $2$ and four $1s$. We can place the $2$ 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 $3$ and the rest $1s$, the sequence will contain one $3$ and three $1s$. We can place the $3$ in either the first, second, third, or fourth position, giving a total of four possibilities. For sequences which contain exactly two $2s$ and the rest $1s$, the sequence will contain two $2s$ and two $1s$. The two $2s$ could be next to each other, separated by one $1$ in between, or separated by two $1s$ in between. We can place the two $2s$ next to each other in three ways, separated by one $1$ in two ways, and separated by two $1s$ in only one way. This gives us a total of six ways to create a sequence which contains two $2s$ and two $1s$. Note that we cannot have a sequence of only $2s$ and $3s$ since the sum will either be $5$ or greater than $6$. We now only need to consider the case where we use all three numbers in the sequence. Since all three numbers add to $6$, the number of permutations of the three numbers is $3!=6$. Adding up the number of sequences above, we get: $3+5+4+6+6=24$. Thus, answer choice $\boxed{\textbf{(E)}\ 24}$ is correct.

## Solution 2

A recursive 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 3

Complementary counting is also possible. Considering the six steps, Jo has to land on the last step, so there are $2^5=32$ ways to land on 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. -adyj

## Video Solution

~ pi_is_3.14

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 