Results 1 to 9 of 9

Thread: Climbing 10 Steps

  1. #1
    Expert Member
    Join Date
    Jun 2006
    Answers
    410

    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.


  2. #2
    Junior Member
    Join Date
    May 2007
    Answers
    3

    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


  3. #3
    Junior Member
    Join Date
    May 2007
    Answers
    3

    Re: Climbing 10 Steps

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


  4. #4
    Contributing Member
    Join Date
    Sep 2006
    Answers
    962

    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


  5. #5
    Contributing Member
    Join Date
    Sep 2006
    Answers
    962

    Re: Climbing 10 Steps

    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


  6. #6
    Contributing Member
    Join Date
    Sep 2006
    Answers
    962

    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


  7. #7
    Expert Member
    Join Date
    Jun 2006
    Answers
    410

    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.


  8. #8
    Junior Member
    Join Date
    Jul 2007
    Answers
    14

    Re: Climbing 10 Steps

    superb james..


  9. #9

    Re: Climbing 10 Steps

    superb james


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
About us
Applying for a job can be a stressful and frustrating experience, especially for someone who has never done it before. Considering that you are competing for the position with a at least a dozen other applicants, it is imperative that you thoroughly prepare for the job interview, in order to stand a good chance of getting hired. That's where GeekInterview can help.
Interact