Difference between revisions of "2005 Alabama ARML TST Problems/Problem 10"
m (alternative solution) |
m (\[\] --> $$) |
||
| Line 2: | Line 2: | ||
When Jon Stewart walks up stairs he takes one or two steps at a time. His stepping sequence is not necessarily regular. He might step up one step, then two, then two again, then one, then one, and then two in order to climb up a total of 9 steps. In how many ways can Jon walk up a 14 step stairwell? | When Jon Stewart walks up stairs he takes one or two steps at a time. His stepping sequence is not necessarily regular. He might step up one step, then two, then two again, then one, then one, and then two in order to climb up a total of 9 steps. In how many ways can Jon walk up a 14 step stairwell? | ||
| + | __TOC__ | ||
==Solution== | ==Solution== | ||
=== Solution 1 === | === Solution 1 === | ||
He can either take 14 one-steps, or 12 one-steps and 1 two-step, etc., so we have | He can either take 14 one-steps, or 12 one-steps and 1 two-step, etc., so we have | ||
| − | < | + | <cmath>\begin{eqnarray*} |
\frac{14!}{14!}+\frac{13!}{12!\cdot 1!}+\frac{12!}{10!\cdot 2!}+\frac{11!}{8!\cdot 3!}+\frac{10!}{6!\cdot 4!}+\frac{9!}{4!\cdot 5!}+\frac{8!}{2!\cdot 6!}+\frac{7!}{7!}\\ | \frac{14!}{14!}+\frac{13!}{12!\cdot 1!}+\frac{12!}{10!\cdot 2!}+\frac{11!}{8!\cdot 3!}+\frac{10!}{6!\cdot 4!}+\frac{9!}{4!\cdot 5!}+\frac{8!}{2!\cdot 6!}+\frac{7!}{7!}\\ | ||
=1+13+66+165+210+126+28+1=14+231+336+29=245+365=\boxed{610} | =1+13+66+165+210+126+28+1=14+231+336+29=245+365=\boxed{610} | ||
| − | \end{eqnarray}</ | + | \end{eqnarray*}</cmath> |
=== Solution 2 === | === Solution 2 === | ||
Let <math>a_n</math> represent the number of sequences of steps that can be taken up the stairs. Clearly <math>a_{1} = 1, a_{2} = 2</math>. Any sequence of length <math>n + 1</math> is either composed of a sequence of length <math>n</math> followed by another step or a sequence of length <math>n-1</math> followed by two steps. Thus we have the recursion | Let <math>a_n</math> represent the number of sequences of steps that can be taken up the stairs. Clearly <math>a_{1} = 1, a_{2} = 2</math>. Any sequence of length <math>n + 1</math> is either composed of a sequence of length <math>n</math> followed by another step or a sequence of length <math>n-1</math> followed by two steps. Thus we have the recursion | ||
| − | + | <cmath> | |
a_{n + 1} = a_{n} + a_{n - 1} | a_{n + 1} = a_{n} + a_{n - 1} | ||
| − | + | </cmath> | |
which indeed is the Fibonacci sequence, except with indexes shifted. Matching them, we have <math>a_n = F_{n + 1}</math>, and <math>a_{14} = F_{15} = \boxed{610}</math>. | which indeed is the Fibonacci sequence, except with indexes shifted. Matching them, we have <math>a_n = F_{n + 1}</math>, and <math>a_{14} = F_{15} = \boxed{610}</math>. | ||
Latest revision as of 17:22, 1 March 2008
Problem
When Jon Stewart walks up stairs he takes one or two steps at a time. His stepping sequence is not necessarily regular. He might step up one step, then two, then two again, then one, then one, and then two in order to climb up a total of 9 steps. In how many ways can Jon walk up a 14 step stairwell?
Solution
Solution 1
He can either take 14 one-steps, or 12 one-steps and 1 two-step, etc., so we have
Solution 2
Let 
represent the number of sequences of steps that can be taken up the stairs. Clearly 
. Any sequence of length 
is either composed of a sequence of length 
followed by another step or a sequence of length 
followed by two steps. Thus we have the recursion
![\[a_{n + 1} = a_{n} + a_{n - 1}\]](http://latex.artofproblemsolving.com/2/4/e/24ea72de8ad8e9ead04a363ffe7769aedcbe4d6c.png)
which indeed is the Fibonacci sequence, except with indexes shifted. Matching them, we have 
, and 
.
See also
| 2005 Alabama ARML TST (Problems) | ||
| Preceded by: Problem 9 |
Followed by: Problem 11 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
