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

(Solution2)
m (Solution 3)
(36 intermediate revisions by 23 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 two <math>2s</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 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>.  
  
==Solution2==
+
There are three possible sequences which only contain one number- all the <math>1s</math>, all <math>2s</math>, or all <math>3s</math>.
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:  
+
 
 +
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:  
 
(<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 14: Line 30:
 
(<math>3</math>)
 
(<math>3</math>)
  
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=<math>7</math> ways to get to step 4. The pattern can then be extended:
+
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 <math>1+2+4=7</math> ways to get to step 4. The pattern can then be extended:
4 steps: 1+2+4=7 ways.
+
<math>4</math> steps: <math>1+2+4=7</math> ways.
5 steps: 2+4+7=13 ways.
+
<math>5</math> steps: <math>2+4+7=13</math> ways.
6 steps: 4+7+13=24 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 <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. -adyj
 +
 
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/5UojVH4Cqqs?t=4560
 +
 
 +
~ pi_is_3.14
 +
 
 +
==Video by MathTalks==
 +
 
 +
https://youtu.be/mSCQzmfdX-g
 +
 
 +
 
  
Thus, there are <math>\boxed{24}</math> ways to get to step 6.
 
  
 
==See Also==
 
==See Also==
 
{{AMC8 box|year=2010|num-b=24|after=Last Problem}}
 
{{AMC8 box|year=2010|num-b=24|after=Last Problem}}
 +
{{MAA Notice}}

Revision as of 19:32, 27 May 2023

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.

  • 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 $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$ 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. -adyj

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 (ProblemsAnswer KeyResources)
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