wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> number of ways to reach Nth step using 1 or 2 step
        
(Message started by: amirivija on Dec 26^th, 2007, 8:43am)

Title: number of ways to reach Nth step using 1 or 2 step
Post by amirivija on Dec 26^th, 2007, 8:43am

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

Title: Re: number of ways to reach Nth step using 1 or 2
Post by amirivija on Dec 26^th, 2007, 8:56am

The destination is n steps away from the start.

Say that the number of single steps taken is m
Hence the number of double steps that need to be taken are (N-m)/2
where m can take the values {0,2,4,..N} if N is even
or {1,3,5.. N} if N is even.

The solution that comes to my mind is, it is the number of ways single steps can fill the places between the double steps (when the number of double steps are greater than number of single steps) and vice versa (when the number of single steps are greater than number of double steps).

summation over m{(0,2,4,..floor[(N+2)/3])|(1,3,5...floor[(N+2)/3])} ^((N-m)/2)+1 C _m + summation over m ceiling[(N+2)/3] ^m+1C _(N-m)/2

Title: Re: number of ways to reach Nth step using 1 or 2
Post by towr on Dec 26^th, 2007, 9:00am

hint 1: [hide]linear recurrence equation[/hide]
hint 2: [hide]Fibonacci[/hide]

Title: Re: number of ways to reach Nth step using 1 or 2
Post by amirivija on Dec 26^th, 2007, 9:24am

hi towr, the solution that you mentioned works fine..

f_n=f_n-1+f_n-2

could you please explain the logic behind this ?

the solution I posted based upon the combination of steps also works.. is there something wrong with it..

Title: Re: number of ways to reach Nth step using 1 or 2
Post by SMQ on Dec 26^th, 2007, 9:44am

on 12/26/07 at 09:24:09, amirivija wrote:

could you please explain the logic behind this ?

For the last move, you can reach step N from step N-1 by moving one, or from step N-2 by moving two; thus the number of ways to reach step N is the number of ways to reach step N-1 plus the number of ways to reach step N-2 -- i.e. f_N = f_N-1 + f_N-2 -- which is exactly the Fibonacci recurrence.

I haven't checked your combinatoric answer, but if it gives the same results then it's correct. ;)

--SMQ

Title: Re: number of ways to reach Nth step using 1 or 2
Post by towr on Dec 26^th, 2007, 10:00am

on 12/26/07 at 09:24:09, amirivija wrote:

could you please explain the logic behind this ?

It's just as SMQ said; so no need for me to repeat it. But I can add that it helps to be familiar with Fibonacci numbers; this problem is equivalent to finding the number of ways of tiling a 2xN board with dominoes (2x1 tiles), which I know to be equivalent to the Fibonacci sequence.

Quote:

the solution I posted based upon the combination of steps also works.. is there something wrong with it..

Your solution seems a bit complicated; but the reasoning makes sense.
It should be possible to simplify it (although it's probably easier to show that it fits the recurrence than blindly working towards something simpler))

A closed expression can be given by taking http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif = (1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif(5))/2;
the number of steps to get to Nth (starting at 1) is then http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif^N/http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif5 [edit]rounded to the nearest integer (as pointed out by Grimbal)[/edit]

Title: Re: number of ways to reach Nth step using 1 or 2
Post by Grimbal on Dec 26^th, 2007, 11:49am

... rounded.

Title: Re: number of ways to reach Nth step using 1 or 2
Post by raj1 on Feb 4^th, 2008, 9:35pm

"finding the number of ways of tiling a 2xN board with dominoes (2x1 tiles), which I know to be equivalent to the Fibonacci sequence. "

Could u please explain this problem or provide a link to this problem. I couldn't find the topic on the forum search.

Title: Re: number of ways to reach Nth step using 1 or 2
Post by towr on Feb 5^th, 2008, 1:19am

on 02/04/08 at 21:35:24, raj1 wrote:

http://mathworld.wolfram.com/FibonacciNumber.html
About halfway down the page it mentions:
"The Fibonacci number F_n+1 gives the number of ways for 2x1 dominoes to cover a 2xn checkerboard, as illustrated in the diagrams above (Dickau)."

(Wikipedia probably also mentions it.)

Title: Re: number of ways to reach Nth step using 1 or 2
Post by Eigenray on Feb 5^th, 2008, 12:25pm

Think of the board as being length N in the horizontal direction. For each step of length 1, put a tile vertically. For each step of length 2, put two tiles horizontally on top of each other. This gives a bijection between the ways to write N as an ordered sum of 1s and 2s, and the number of 2x1 tilings of a 2xN board.

Title: Re: number of ways to reach Nth step using 1 or 2
Post by foobar on Jul 9^th, 2008, 12:53pm

Max num of steps possible = N (only single steps)
num of ways = 1
When num of double steps is 1 = N-1
num of ways = (N-1)C1
When num of double steps is 2 = N-2
num of ways = (N-2)C2
...
When num of double steps is [N/2] (max)= [N/2]
num of ways = (N-N/2) * C (N/2)
_n=N/2
Total num of ways = summation ^N-nCⁿ
ⁿ⁼⁰