Math Circle Sample Question

Walking Stairs

Suppose I am standing at the base of an infinite staircase.

How many different ways are there for me to walk one step up and walk one step down? This answer is simple, just one way: up then down. Why? I can't step down since I am at the base of the staircase.

Now, how many ways different can I walk two steps up and two steps down in whatever order I like?  Here’s one way: up, up, down, down. Here’s another: up, down, up, down. However, I cannot walk up, down, down, up (why not?).

Question 1: How many ways are there to walk 3 steps up and 3 steps down?

Question 2: How many ways are there to walk 4 steps up and 4 steps down?

Question 3: Find a systematic way to list all ways to go up 5 steps and down 5 steps. How many ways are there?

Question 4: Generalize. Looking at your answers to the previous three questions, can you find a way to generate the other numbers in the sequence without actually listing all the possible walks? Look for repeated structure in this problem, can you reuse the work you’ve already done for a smaller version of the problem to solve the larger version?

Where’s the math?

  • Persistence in solving a problem
  • Analysing solutions for correctness
  • Working small cases and generalizing
  • Organizing data
  • Looking and reusing repeated structure