## 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?

January 8th, 2011 at 1:14 pm

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.

January 8th, 2011 at 1:16 pm

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!

January 8th, 2011 at 1:18 pm

I should have typed quicker! lol

January 8th, 2011 at 8:05 pm

I’ve noticed that too curtis

January 8th, 2011 at 9:14 pm

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

January 8th, 2011 at 11:32 pm

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?

January 9th, 2011 at 7:39 am

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?!?!?!

January 10th, 2011 at 1:06 pm

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”.

January 10th, 2011 at 3:54 pm

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.

January 10th, 2011 at 3:55 pm

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

January 14th, 2011 at 10:44 am

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

January 14th, 2011 at 11:46 am

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

January 14th, 2011 at 3:54 pm

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.