Subscribe via feed.

The Staircase

Posted by Karl Sharman on January 8, 2011 – 11:56 am

It is possible to climb three steps in exactly four different ways.
Ie:-
step 1 step 2 and step 3
step 1 step 3
step 2 step 3
step 3

How many ways can you climb ten steps? And for further entertainment – twenty steps?

Tags:
This post is under “Tom” and has 13 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

13 Responds so far- Add one»

  1. 1. Nathan Said:

    If I understand the question, then the pattern outlined above follows a row of pascal’s triangle. The is one way to go up the stairs one at a time, two ways to go up with steps of one and two, and one way to go up the stairs all at once. To solve for the ten step version, we just need to add that row, which has the same value as 2^(10-1), or 512 different ways for ten steps. For twenty steps, that is 2^(20-1) or 524288 different ways.

  2. 2. Curtis Said:

    I may be sticking my neck out but the no.of ways appears to double with each additional step.

    2 steps…..2
    3 steps…..4
    4 steps…..8

    so for n steps, no. of ways = 2^(n-1)

    so
    10 steps = 512
    20 steps = 524,288

    and very long legs!

  3. 3. Curtis Said:

    I should have typed quicker! lol

  4. 4. Nathan Said:

    I’ve noticed that too curtis

  5. 5. Chris Said:

    Let N(S) be the number of ways we can climb S steps.
    To get to a given step, S, we can go from each of the previous cases to the final step, plus one additional direct transition to the Sth step.

    i.e. N(S) = 1 + N(1) + N(2) + … + N(S-1)
    and N(S+1) = 1 + N(1) + N(2) + … + N(S-1) + N(S)
    Substituting the RHS of the first equation into the second =>
    N(S+1) = 2*N(S) => N(S+2) = 2*N(S+1) = 2*2*N(S)
    And continuing => N(S+n) = 2^n*N(S)
    But N(1) = 1, so N(1+n) = 2^n
    Substituting 1+n = S => N(S) = 2^(S-1). NB S > 0.

    So N(10) = 2^9 = 512 and N(20) = 2^19 = 524 288

  6. 6. Chris Said:

    The intro to the above was a little vague. What I meant was is that you can go to the final step from each of the end points of all the previous cases (from the 1 step case, the 2 steps case, etc.)

    I’m quite intrigued by recursive/induction formulae. In particular in the way that they fail. e.g. If in the above you plug in #steps = 1, you get 1/2 a way of doing it. What the heck does that mean?

  7. 7. kcj neththie Said:

    at first i came to the same conclusion..but bcoz of the nature of this Q, we can not apply the above method..a person can climb 3 steps at once in a ordinary stair case..4 may be.. but its impossible to clim 9,10 steps @ onece 2^(n-1) contains those things also..
    so any ideas folks?!?!?!

  8. 8. Euclid's Brother Said:

    What’s the point of having stairs if you can step directly to the top? There should be some max to the number of stiarsteps skiped in each “step”.

  9. 9. Chris Said:

    If I’ve not goofed, then if m is the maximum number of steps that can be taken at once, then the number of ways of climbing s steps is:
    2^(s-1) – 2^(s-m) = 2^(s-1)(1 – 1/2^m), for s > m > 0

    e.g. s = 3, m = 1 => 2^2(1 – 1/2) = 2
    e.g. s = 3, m = 2 => 2^2(1 – 1/4) = 3

    If m = 3, a reasonable value, the correction factor is 1 – 1/8 = 7/8.

  10. 10. Chris Said:

    aaargh that was supposed to be 2^(s-1) – 2^(s-1-m), the rest is unchanged.

  11. 11. cazayoux Said:

    I like Euclid’s Brother’s suggestion.

    What is the number of ways to climb 10 stairs..
    .. if only allowed to take one stair at a time?
    .. if allowed one or two stairs at a time?
    .. if allowed one, two, or three, at a time?

    100 stairs?
    X stairs?

    one example of the solution for 10 stairs might be…
    1 step, 1 step, 2 steps, 3 steps, 1 step, 2 steps.

    michel

  12. 12. Chris Said:

    Hi cazayoux. I’ve already answered that question in post 9.

  13. 13. Chris Said:

    Your one, two, three at a time is the same at most three at a time, that’s what my “m” is.

    If you can only take a fixed number of steps (n) then s/n is the approximate answer.

    If you have 100 stairs and are allowed to take at most 4 steps at a time, then there are 2^(100-1) * (1 – 1/2^4)
    = 594211218856982531951579627520 steps, rather than
    633825300114114700748351602688 wheb you can take as many steps at a time as you wish. The difference is only 1/16 th
    Unless I have goofed.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0