## Wednesday, August 20, 2014

### Notes to Sunday Nights' Problem Solving Group Lessons

This week's work : Please review the last 8 hardest AMC-8 problems from 2005 to 2011 + finish the last 8 hardest AMC-8 problems from 2012 and 2013 if you haven't done that.

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.

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.

#1 : 57

#2 : 6

#3 : 50