Author |
Topic: number of ways to reach Nth step using 1 or 2 step (Read 6249 times) |
|
amirivija
Newbie
Posts: 8
|
 |
number of ways to reach Nth step using 1 or 2 step
« on: Dec 26th, 2007, 8:43am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
amirivija
Newbie
Posts: 8
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #1 on: Dec 26th, 2007, 8:56am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #2 on: Dec 26th, 2007, 9:00am » |
Quote Modify
|
hint 1: linear recurrence equation
hint 2: Fibonacci
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
amirivija
Newbie
Posts: 8
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #3 on: Dec 26th, 2007, 9:24am » |
Quote Modify
|
hi towr, the solution that you mentioned works fine..
fn=fn-1+fn-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..
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #4 on: Dec 26th, 2007, 9:44am » |
Quote Modify
|
on Dec 26th, 2007, 9:24am, 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. fN = fN-1 + fN-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
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #5 on: Dec 26th, 2007, 10:00am » |
Quote Modify
|
on Dec 26th, 2007, 9:24am, 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  = (1+ (5))/2;
the number of steps to get to Nth (starting at 1) is then N/5 [edit]rounded to the nearest integer (as pointed out by Grimbal)[/edit]
|
| « Last Edit: Dec 26th, 2007, 12:06pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #6 on: Dec 26th, 2007, 11:49am » |
Quote Modify
|
... rounded.
|
|
IP Logged |
|
|
|
raj1
Newbie
Posts: 15
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #7 on: Feb 4th, 2008, 9:35pm » |
Quote Modify
|
"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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #8 on: Feb 5th, 2008, 1:19am » |
Quote Modify
|
on Feb 4th, 2008, 9:35pm, raj1 wrote:"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. |
|
http://mathworld.wolfram.com/FibonacciNumber.html
About halfway down the page it mentions:
"The Fibonacci number Fn+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.)
|
| « Last Edit: Feb 5th, 2008, 1:21am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #9 on: Feb 5th, 2008, 12:25pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
foobar
Newbie
Posts: 7
|
|
Re: number of ways to reach Nth step using 1 or 2
« Reply #10 on: Jul 9th, 2008, 12:53pm » |
Quote Modify
|
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-nCn
n=0
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print