Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 AMC 8 Problems/Problem 25"

m (→‎Solution 3 (Recursion))
m (→‎Solution 3 (Recursion))
Line 24: Line 24:
  
 
==Solution 3 (Recursion)==
 
==Solution 3 (Recursion)==
−
We can set up a recursion to solve this problem. Suppose <math>f(n)</math> represents the number of valid ways to get to the <math>n</math>th step. <math>f(0)=1</math> because there is 1 way for Jo to get to the "<math>0</math>th" step (i.e. the ground). There is <math>1</math> way to get to the first step (a <math>1</math>-step), so <math>f(1)=1</math>. There are <math>2</math> ways to get to the second step (two <math>1</math>-steps or one <math>2</math>-step). In general, <math>f(n) = f(n-1) + f(n-2) + f(n-3)</math>. This is because from the <math>n-3</math>th step, Jo can take a <math>3</math>-step to get to the <math>n</math>th step, from the <math>n-2</math>th step, Jo can take a <math>2</math>-step to get to the <math>n</math>th step, and from the <math>n-1</math>th step, Jo can take a <math>1</math>-step to get to the <math>n</math>th step. We now iteratively calculate values of <math>f(n)</math>.
+
We can set up a recursion to solve this problem. Suppose <math>f(n)</math> represents the number of valid ways to get to the <math>n</math>th step. <math>f(0)=1</math> because there is 1 way for Jo to get to the "<math>0</math>th" step (i.e. the ground). There is <math>1</math> way to get to the first step (a <math>1</math>-step), so <math>f(1)=1</math>. There are <math>2</math> ways to get to the second step (two <math>1</math>-steps or one <math>2</math>-step). Thus, <math>f(2) = 2</math>. In general, <math>f(n) = f(n-1) + f(n-2) + f(n-3)</math>. This is because from the <math>n-3</math>th step, Jo can take a <math>3</math>-step to get to the <math>n</math>th step, from the <math>n-2</math>th step, Jo can take a <math>2</math>-step to get to the <math>n</math>th step, and from the <math>n-1</math>th step, Jo can take a <math>1</math>-step to get to the <math>n</math>th step. We now iteratively calculate values of <math>f(n)</math>.
  
  

Revision as of 12:14, 26 January 2024

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.

Solution 3 (Recursion)

We can set up a recursion to solve this problem. Suppose $f(n)$ represents the number of valid ways to get to the $n$th step. $f(0)=1$ because there is 1 way for Jo to get to the "$0$th" step (i.e. the ground). There is $1$ way to get to the first step (a $1$-step), so $f(1)=1$. There are $2$ ways to get to the second step (two $1$-steps or one $2$-step). Thus, $f(2) = 2$. In general, $f(n) = f(n-1) + f(n-2) + f(n-3)$. This is because from the $n-3$th step, Jo can take a $3$-step to get to the $n$th step, from the $n-2$th step, Jo can take a $2$-step to get to the $n$th step, and from the $n-1$th step, Jo can take a $1$-step to get to the $n$th step. We now iteratively calculate values of $f(n)$.


$f(0) = 1$

$f(1) = 1$

$f(2) = 2$

$f(3) = f(2) + f(1) + f(0) = 2 + 1 + 1 = 4$

$f(4) = f(3) + f(2) + f(1) = 4 + 2 + 1 = 7$

$f(5) = f(4) + f(3) + f(2) = 7 + 4 + 2 = 13$

$f(6) = f(5) + f(4) + f(3) = 13 + 7 + 4 = \boxed{\textbf{(E) 24}}$

~ cxsmi

Video Solution by OmegaLearn

https://youtu.be/5UojVH4Cqqs?t=4560

~ pi_is_3.14

Video by MathTalks

https://youtu.be/mSCQzmfdX-g



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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_AMC_8_Problems/Problem_25&oldid=213007"