
Expert Member
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.

Junior Member
Re: Climbing 10 Steps
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

Junior Member
Re: Climbing 10 Steps
So we can get the answer easily, that is 6 ways to climb 10 steps

Contributing Member
Re: Climbing 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

Contributing Member
Re: Climbing 10 Steps
The answer for this question is 89.
Solution:
Following combination will show the number of 1step and 2step 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

Contributing Member
Re: Climbing 10 Steps
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

Expert Member
Re: Climbing 10 Steps
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.

Junior Member

Junior Member
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules