Thread: Climbing 10 Steps

Here is one more question on Permutations.

Find the number of ways in which you can climb 10 steps if you can go up 1 or 2 steps at a time.

assume the number of going up 1 step is x, and the other is y, then I can do the equation:
x+2y=10
and because 2y is even so the must satify the formula below:
x mod 2=0

So we can get the answer easily, that is 6 ways to climb 10 steps

hi iami007,

Surely your answer is not correct. Because look at this sentence "you can go up 1 or 2 steps at a time".

According to your calculation, you are assuming first time move one step and next time move two step. That is not mandatory.

Here i post more then 6 ways for you...

1. Use ten single step to reach the top.
2. Use first two step as single and remaining as two.
3. Use first four step as single and remaining as two.
4. Use first six step as single and remaining as two.
5. Use first eight step as single and remaining as two.
6. Use five two steps to reach the top.
7. Use first step as two and remaining as single.
8. Use two step as two and remaining as single..
.....
.....
and so on....

I think now you clear about james question..Try to find the answer.

---------------------
suresh

The answer for this question is 89.

Solution:

Following combination will show the number of 1-step and 2-step jumps needed for completing 10 steps.

(10,0) (8,1) (6,2) (4,3) (2,4) (0,5)

Now the question is, "For each of these possibilities, how many ways
can the different steps be arranged?".

Lets take the first one (10,0). Here only one way to complete the 10 steps.
Next (8,1). Here you can get 9 ways to complete the 10 steps.
The nine ways are as follows...
(2,1,1,1,1,1,1,1,1)
(1,2,1,1,1,1,1,1,1)
(1,1,2,1,1,1,1,1,1)
(1,1,1,2,1,1,1,1,1)
(1,1,1,1,2,1,1,1,1)
(1,1,1,1,1,2,1,1,1)
(1,1,1,1,1,1,2,1,1)
(1,1,1,1,1,1,1,2,1)
(1,1,1,1,1,1,1,1,2)
Like these ways we get the number of way from the following combination.
(6,2) - we can get 28 ways.
(4,3) - we can get 35 ways.
(2,4) - we can get 15 ways.
(0,5) - we can get 1 way.

So the total number of ways to climbing 10 steps is.
1+9+28+35+15+1 = 89.

-----------------------------
suresh

After i found the above solution, i am thinking if someone want 100 steps or 1000 steps then how can i find it..? So we can't able to do the same grunt work.

So i requested to james give the general solution for this problem...Anyway i found the answer for this question..

-------------------
suresh

lf number of steps is 1.

IF number of steps =2
There are two different ways to finish 11,2

If number of steps =3
There are three different ways to finish 111,12,21

If number of steps =4
There are five different ways to finish 1111,112,121,211,22


If number of steps =5
There are eight different ways to finish 11111,1112,1121,1211,2111,122,212,221

If u closely look at the numbers you can find that they are numbers of fibonacci series (1,2,3,5,8...) and 89 is also a fibonacci number.

fibonacci numbers are

0,1,1,2,3,5,8,13...

for 1 step, number of different ways is 1 (3rd fibonacci number)
for 2 steps number of different ways is 2 (4rd fibonacci number)
for 3 steps number of different ways is 3 (5rd fibonacci number)

But it is not easy to calculate 100th fibonacci number manually. I don't think we have a formula in place to find the accurate value of nth fibonacci number.

superb james..

superb james