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"

(→‎Problem)
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
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?
+
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 1==
 
==Solution 1==
−
A valid climb is a sequence of some or all of the <math>1</math>, <math>2</math>, and <math>3</math> step hops, in which the sum of the sequence adds to <math>6</math>.
 
−
 
−
There are three possible sequences which only contain one number- all the <math>1s</math>, all <math>2s</math>, or all <math>3s</math>.
 
−
 
−
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.
 
−
 
−
*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 <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:  
 
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:  
 
(<math>1</math>,<math>1</math>,<math>1</math>)
 
(<math>1</math>,<math>1</math>,<math>1</math>)
Line 37: Line 18:
 
Thus, there are <math>\boxed{\textbf{(E) } 24}</math> ways to get to step <math>6.</math>
 
Thus, there are <math>\boxed{\textbf{(E) } 24}</math> ways to get to step <math>6.</math>
  
−
==Solution 3==
 
−
Complementary counting is also possible. Considering the six steps, Jo has to land on the last step, so there are <math>2^5=32</math> subsets (hit steps) of the other five steps. After that, subtract the number of ways to climb the steps while taking a leap of <math>4</math>, <math>5</math>, or <math>6</math>. The eight possible ways for this is (<math>4</math>, <math>1</math>, <math>1</math>), (<math>4</math>, <math>2</math>), (<math>1</math>, <math>4</math>, <math>1</math>), (<math>1</math>, <math>1</math>, <math>4</math>), (<math>2</math>, <math>4</math>), (<math>1</math>, <math>5</math>), (<math>5</math>, <math>1</math>), and (<math>6</math>)
 
  
−
Altogether this makes for <math>32-8= \boxed{\textbf{(E) 24}}</math> valid ways for Jo 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 <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
 +
 
 +
 
  
−
== Video Solution by OmegaLearn ==
 
 
https://youtu.be/5UojVH4Cqqs?t=4560
 
https://youtu.be/5UojVH4Cqqs?t=4560
  

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"