Some notes and questions.
Question #1 : How many ways can you climb up a ten-step staircase if you climb only one or two steps at a time ?
Solutions I :
Make a chart, starting with a smaller case.
one-step staircase -- 1 way, which is 1.
two-step staircase -- 2 ways, which is 1, 1 or 2.
three-step staircase -- 3 ways, which is 1 1 1, 1 2 or 2 1.
four-step staircase -- 5 ways, which is 1111, 211, 121, 112, 2222.
Notice the pattern - - 1 , 2, 3, 5, 8, 13, 21, 34, 55, 89, which is the answer; it also happens that it's
part of the Fibonacci numbers.
Why does it work that way ?
Well, if you climb the 3-step staircase, there are two cases :
You either take one step at first, and there are 2-step left, which leaves you two ways to climb the remaining staircase.
Or you take two step at first, and there are 1 step left, which leaves you one way to climb the remaining staircase.
If you climb the 4-step staircase, again, there are two similar cases :
You either take one step at first, and then there are 3-step left, which leaves you 3 ways to climb the remaining staircase.
Or you take two step at first, and there are 2 step left, which leaves you 2 way to climb the remaining staircase.
Thus, it's always the sum of the previous two terms for the next staircase steps.
This concept is called recursion.
Now try another question :
2010 AMC-8 #25 : Every day at school, Jo climbs a flight of 6 stairs. Joe 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 ?
Solution I :
List out all the possible ways.
111111 -- 1 way
21111 -- 5C1 = 5 ways to arrange the steps
2211 -- 4!/2! x 2! = 6 ways to arrange the steps
222-- 1 way
3111 -- 4C1 or 4 ways to arrange the steps
123 -- 3! or 6 ways
33 -- 1 way
Sum them up and the answer is 24.
Solution II :
Using recursion, starting with the smallest case.
1 step -- 1 way
2 steps-- 2 ways (11, or 2)
3 steps -- 4 ways (111, 21, 12, or 3)
4 steps -- 1 + 2 + 4 = 7 ways (why??)
5 steps -- 2 + 4 + 7 = 13 ways.
6 steps -- 4 + 7 + 13 = 24 ways, which is the answer.
Besides these, please review the following questions.
Answer key below.
Q #1 1988 AMC-8 #25 : A palindrome is a whole number that reads the same forwards as backwards. If one neglects the colon, certain times displayed on a digital watch are palindromes. Three examples are 1: 01, 4: 44 and 12: 21. How many times during a 12-hour period will be palindromes?
Q#2 2004 Mathcounts sprint #21: If |-2a + 1| < 13, what is the sum of the distinct possible integer values of a?
Q#3 2004 Mathcounts sprint #30 : A particular right square-based pyramid has a volume of 63,960 cubic meters and a height of 30 meters. What is the number of meters in the length of the lateral height (AB) of the pyramid? Express your answer to the nearest whole number.
Answer key :
#1 : 57
#2 : 6
#3 : 50
