|
|
(26 intermediate revisions by 12 users not shown) |
Line 5: |
Line 5: |
| | | |
| ==Solution 1== | | ==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==
| |
− | A recursive 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 21: |
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== | + | == Video Solution by OmegaLearn == |
− | 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> ways to land on 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:
| + | https://youtu.be/5UojVH4Cqqs?t=4560 |
− | | |
− | (<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>)
| + | ~ pi_is_3.14 |
| | | |
− | (<math>2</math>, <math>4</math>)
| + | ==Video by MathTalks== |
| | | |
− | (<math>1</math>, <math>5</math>)
| + | https://youtu.be/mSCQzmfdX-g |
| | | |
− | (<math>5</math>, <math>1</math>)
| |
| | | |
− | (<math>6</math>)
| |
| | | |
− | Altogether this makes for <math>32-8=24</math> \boxed{\textbf{(E) } valid ways for Jo to get to step 6. ~adyj
| |
| | | |
| ==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}} | | {{MAA Notice}} |
Problem
Everyday at school, Jo climbs a flight of
stairs. Jo can take the stairs
,
, or
at a time. For example, Jo could climb
, then
, then
. In how many ways can Jo climb the stairs?
Solution 1
A dynamics programming approach is quick and easy. The number of ways to climb one stair is
. There are
ways to climb two stairs:
,
or
. For 3 stairs, there are
ways:
(
,
,
)
(
,
)
(
,
)
(
)
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
ways to get to step 4. The pattern can then be extended:
steps:
ways.
steps:
ways.
steps:
ways.
Thus, there are
ways to get to step
Video Solution by OmegaLearn
https://youtu.be/5UojVH4Cqqs?t=4560
~ pi_is_3.14
Video by MathTalks
https://youtu.be/mSCQzmfdX-g
See Also
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.