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)
 
(41 intermediate revisions by 21 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
Everyday at school, Jo climbs a flight of <math>6</math> stairs. Joe can take the stairs <math>1</math>, <math>2</math>, or <math>3</math> at a time. For example, Jo could climb <math>3</math>, then <math>1</math>, then <math>2</math>. In how many ways can Jo climb the stairs?
+
Everyday at school, Jo 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, Jo could climb <math>3</math>, then <math>1</math>, then <math>2</math>. In how many ways can Jo 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>
  
−
==Solution==
+
==Solution 1==
−
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 <math>1</math>, <math>2</math>, and <math>3</math>, in which the sum of the sequence adds to <math>6</math>. Since there is only one way to create a sequence which contains all <math>1s</math>, all <math>2s</math>, or all <math>3s</math>, there are three possible sequences which only contain one number. If we attempt to create sequences which contain one <math>2</math> and the rest <math>1s</math>, the sequence will contain one <math>2</math> and four <math>1s</math>. We can place the <math>2</math> 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 <math>3</math> and the rest <math>1s</math>, the sequence will contain one <math>3</math> and three <math>1s</math>. We can place the <math>3</math> in either the first, second, third, or fourth position, giving a total of four possibilities. For sequences which contain exactly two <math>2s</math> and the rest <math>1s</math>, the sequence will contain two <math>2s</math> and two <math>1s</math>. The two <math>2s</math> could be next to each other, separated by one <math>1</math> in between, or separated by two <math>1s</math> in between. We can place the two <math>2s</math> next to each other in three ways, separated by one <math>1</math> in two ways, and separated by two <math>1s</math> in only one way. This gives us a total of six ways to create a sequence which contains two <math>2s</math> and two <math>1s</math>. Note that we cannot have a sequence of only <math>2s</math> and <math>3s</math> since the sum will either be <math>5</math> or greater than <math>6</math>. We now only need to consider the case where we use all three numbers in the sequence. Since all three numbers add to <math>6</math>, the number of permutations of the three numbers is <math>3!=6</math>. Adding up the number of sequences above, we get: <math>3+5+4+6+6=24</math>. Thus, answer choice <math>\boxed{\textbf{(E)}\ 24}</math> is correct.
+
A dynamics programming approach is quick and easy. The number of ways to climb one stair is <math>1</math>. There are <math>2</math> ways to climb two stairs: <math>1</math>,<math>1</math> or <math>2</math>. For 3 stairs, there are <math>4</math> ways:  
−
 
 
−
==Solution 2==
 
−
An inductive approach is quick and easy. The number of ways to climb one stair is <math>1</math>. There are <math>2</math> ways to climb two stairs: <math>1</math>,<math>1</math> or <math>2</math>. For 3 stairs, there are four ways:  
 
 
(<math>1</math>,<math>1</math>,<math>1</math>)
 
(<math>1</math>,<math>1</math>,<math>1</math>)
 
(<math>1</math>,<math>2</math>)
 
(<math>1</math>,<math>2</math>)
Line 19: Line 16:
 
<math>6</math> steps: <math>4+7+13=24</math> ways.
 
<math>6</math> steps: <math>4+7+13=24</math> ways.
  
−
Thus, there are <math>\boxed{\textbf{(E) } 24}</math> ways to get to step 6.
+
Thus, there are <math>\boxed{\textbf{(E) } 24}</math> ways to get to step <math>6.</math>
 +
 
 +
 
 +
==Solution 2 (Generating a Function)==
 +
We first start by doing some simple casework to try and find the number of ways we can get to the 1st, 2nd, and 3rd Stairs. The number of ways to climb one stair is <math>1</math>. There are <math>2</math> ways to climb two stairs: <math>1</math>,<math>1</math> or <math>2</math>. For 3 stairs, there are <math>4</math> ways:
 +
(<math>1</math>,<math>1</math>,<math>1</math>)
 +
(<math>1</math>,<math>2</math>)
 +
(<math>2</math>,<math>1</math>)
 +
(<math>3</math>)
 +
 
 +
Next we must try to generalize a recursive function to find the number of ways to climb the stairs. We start out with <math>f(n)</math>, which denotes the number of ways to climb the stairs. Then we must realize, To reach the nth stair, Jeff must take a 1 step from the <math>f(n-1)</math>th stair, a double step from the <math>f(n-2)</math>th stair, or a triple step from the <math>f(n-3)</math>th stair. Therefore, the number of ways of reaching the nth step is the number of ways of reaching the <math>f(n-1)</math>th plus the number of ways of reaching the <math>f(n-2)</math>th plus the number of ways of reaching the <math>f(n-3)</math>th.
 +
stair. So we have our generalized recursive function: <cmath>f(n)=f(n-1)+f(n-2)+f(n-3)</cmath>
 +
 
 +
Now that we have the function and a few of the values we can try to find <math>f(6)</math>
 +
 
 +
<cmath>f(1)=1</cmath>
 +
<cmath>f(2)=2</cmath>
 +
<cmath>f(3)=f(3-1)+f(3-2)+f(3-3)=f(2)+f(1)+f(0)=2+1+1=4</cmath>
 +
<cmath>f(4)=f(4-1)+f(4-2)+f(4-3)=f(3)+f(2)+f(1)=4+2+1=7</cmath>
 +
<cmath>f(5)=f(5-1)+f(5-2)+f(5-3)=f(4)+f(3)+f(2)=7+4+2=13</cmath>
 +
<cmath>f(6)=f(6-1)+f(6-2)+f(6-3)=f(5)+f(4)+f(3)=13+7+4=24</cmath>
 +
 
 +
Thus there are 24 ways to get to the 6th stair so the answer is <math>\boxed{\textbf{(E) } 24}</math>
 +
 
 +
~ algebraic_algorithmic
 +
 
 +
 
 +
 
 +
https://youtu.be/5UojVH4Cqqs?t=4560
 +
 
 +
~ pi_is_3.14
 +
 
 +
==Video by MathTalks==
 +
 
 +
https://youtu.be/mSCQzmfdX-g
 +
 
 +
 
 +
 
  
 
==See Also==
 
==See Also==
−
{{AMC8 box|year=2010|num-b=809|after=Last Problem}}
+
{{AMC8 box|year=2010|num-b=24|after=Last Problem}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 13:02, 2 January 2025

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 (Generating a Function)

We first start by doing some simple casework to try and find the number of ways we can get to the 1st, 2nd, and 3rd Stairs. 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$)

Next we must try to generalize a recursive function to find the number of ways to climb the stairs. We start out with $f(n)$, which denotes the number of ways to climb the stairs. Then we must realize, To reach the nth stair, Jeff must take a 1 step from the $f(n-1)$th stair, a double step from the $f(n-2)$th stair, or a triple step from the $f(n-3)$th stair. Therefore, the number of ways of reaching the nth step is the number of ways of reaching the $f(n-1)$th plus the number of ways of reaching the $f(n-2)$th plus the number of ways of reaching the $f(n-3)$th. stair. So we have our generalized recursive function: \[f(n)=f(n-1)+f(n-2)+f(n-3)\]

Now that we have the function and a few of the values we can try to find $f(6)$

\[f(1)=1\] \[f(2)=2\] \[f(3)=f(3-1)+f(3-2)+f(3-3)=f(2)+f(1)+f(0)=2+1+1=4\] \[f(4)=f(4-1)+f(4-2)+f(4-3)=f(3)+f(2)+f(1)=4+2+1=7\] \[f(5)=f(5-1)+f(5-2)+f(5-3)=f(4)+f(3)+f(2)=7+4+2=13\] \[f(6)=f(6-1)+f(6-2)+f(6-3)=f(5)+f(4)+f(3)=13+7+4=24\]

Thus there are 24 ways to get to the 6th stair so the answer is $\boxed{\textbf{(E) } 24}$

~ algebraic_algorithmic


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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC logo.png

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