Difference between revisions of "2005 Alabama ARML TST Problems/Problem 10"

(See also)
m (\[\] --> $$)
 
(One intermediate revision by the same user not shown)
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 ===
 
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
  
<math>\begin{eqnarray}
+
<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}</math>
+
\end{eqnarray*}</cmath>
 +
 
 +
=== 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
 +
<cmath>
 +
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>.
  
 
==See also==
 
==See also==
 
{{ARML box|year=2005|state=Alabama|num-b=9|num-a=11}}
 
{{ARML box|year=2005|state=Alabama|num-b=9|num-a=11}}
 +
 +
[[Category:Introductory Combinatorics Problems]]

Latest revision as of 18: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

\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!}\\ =1+13+66+165+210+126+28+1=14+231+336+29=245+365=\boxed{610} \end{eqnarray*}

Solution 2

Let $a_n$ represent the number of sequences of steps that can be taken up the stairs. Clearly $a_{1} = 1, a_{2} = 2$. Any sequence of length $n + 1$ is either composed of a sequence of length $n$ followed by another step or a sequence of length $n-1$ followed by two steps. Thus we have the recursion \[a_{n + 1} = a_{n} + a_{n - 1}\] which indeed is the Fibonacci sequence, except with indexes shifted. Matching them, we have $a_n = F_{n + 1}$, and $a_{14} = F_{15} = \boxed{610}$.

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