Mathematics Puzzle: Climbing up a Staircase

Posted on March 10, 2008
Filed Under Math Puzzles |

Here’s a short little puzzle I was asked at a job interview some time ago.

Suppose you have a staircase with n steps. You wish to climb up the staircase. At each point you either climb up one step, or make a small leap and jump up two steps - just like a normal human being tends to do. The question is, how many different ways can you do that?

For example, given 3 stairs, you can either climb up one stair at a time, or climb up one stair and then two, or two and then one - a total of 3 possibilities.

Can you guess (and prove!) the general answer? I must admit I was a bit surprised when I found it.

Comments

4 Responses to “Mathematics Puzzle: Climbing up a Staircase”

  1. wandering.the.cosmos on March 10th, 2008 10:35 am

    My guess is: # ways = 1 + sum_{i=1}^Floor[n/2] (n-1) (n-3) … (n+1-2i). I have not thought much about how to perform the sum; Mathematica gave me a bizarre answer. As a check, for your n = 3 case, we have Floor[n/2] = 1, and # ways = 1 + (3-1) = 3. For say n = 4, we have Floor[n/2] = 2, and # ways = 1 + (4-1) + (4-1)(4-3) = 7.

  2. admin on March 10th, 2008 11:55 am

    For n=4, your options are:

    1111
    112
    121
    211
    22

    So that’s a total of 5, different from your 7.
    Back to the drawing board :).

  3. wandering.the.cosmos on March 11th, 2008 1:15 pm

    My bad. The answer I believe is given by the sum:

    # ways = sum_{i=0}^{Floor[n/2]} [n-i]!/(i![n-2i]!)

    As a (proper) check, we examine the following:

    [*] n = 2. Floor[n/2] = 1. The sum is then 2!/(0!2!) + 1!/(1!0!) = 2. The two cases are, using your notation,

    11
    2

    [*] n = 3. Floor[n/2] = 1. The sum is then 3!/(0!3!) + 2!/(1!1!) = 1 + 2 = 3. The three cases are,

    111
    21
    12

    [*] n = 4. Floor[n/2] = 2. The sum is then 4!/(0!4!) + 3!/(1!2!) + 2!/(2!0!) = 1 + 3 + 1 = 5. The cases are listed above.

    [*] n = 5. Floor[n/2] = 2. The sum is then 5!/(0!5!) + 4!/(1!3!) + 3!/(2!1!) = 1 + 4 + 3 = 8. The cases are,

    11111
    2111
    1211
    1121
    1112
    221
    212
    122

    I don’t know and haven’t thought much about how to obtain a closed form expression for the sum. Mathematica still gives a bizarre expression in terms of some hypergeometric function.

  4. admin on March 15th, 2008 2:39 pm

    That’s interesting.

    Oddly enough, it’s the right answer - I say “oddly” because I didn’t expect to see it in that form.

    Your series is an expansion of the Chebyshev polynomial of the 2nd kind, which is related to the Pascal triangle. Also related to the Pascal triangle is … the Fibonacci sequence, which, you’ll notice, is the result of your sequence for n=1,2,3,4,… ad infinitum.

    Take a look here:

    http://milan.milanovic.org/math/english/fibo/fibo2.html

    and here:

    http://milan.milanovic.org/math/english/fibo/fibo6.html

    My solution was in terms of recursion. Let An be the number of possible ways for n steps. Suppose we know A(n-2) and A(n-1). What is An? We can either have:

    [sequence of steps] + 1 step at the end = A(n-1) options
    OR:
    [sequence of steps] + 2 steps at the end = A(n-2) options

    So:

    An = A(n-1) + A(n-2)

    Which is precisely the recursion relation which defines the Fibonacci sequence (you can also observe, ps, that A(1)=1, A(2) = 2, which satisfies the initial conditions).

    So - interesting result. I can now say this question surprised me twice! :)

Leave a Reply