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 13:14, 26 January 2024
Contents
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
Solution 2
Complementary counting is also possible. Considering the six steps, Jo has to land on the last step, so there are subsets (hit steps) of the other five steps. After that, subtract the number of ways to climb the steps while taking a leap of
,
, or
. The eight possible ways for this is (
,
,
), (
,
), (
,
,
), (
,
,
), (
,
), (
,
), (
,
), and (
)
Altogether this makes for valid ways for Jo to get to step 6.
Solution 3 (Recursion)
We can set up a recursion to solve this problem. Suppose represents the number of valid ways to get to the
th step.
because there is 1 way for Jo to get to the "
th" step (i.e. the ground). There is
way to get to the first step (a
-step), so
. There are
ways to get to the second step (two
-steps or one
-step). Thus,
. In general,
. This is because from the
th step, Jo can take a
-step to get to the
th step, from the
th step, Jo can take a
-step to get to the
th step, and from the
th step, Jo can take a
-step to get to the
th step. We now iteratively calculate values of
.
~ cxsmi
Video Solution by OmegaLearn
https://youtu.be/5UojVH4Cqqs?t=4560
~ pi_is_3.14
Video by MathTalks
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.