Author |
Topic: Number of ways (Read 624 times) |
|
raj1
Newbie
Posts: 15
|
 |
Number of ways
« on: Feb 4th, 2008, 1:18pm » |
 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 |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
|
Re: Number of ways
« Reply #1 on: Feb 4th, 2008, 2:59pm » |
Quote Modify
|
Discussed recently here (and a variation here).
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Number of ways
« Reply #2 on: Feb 9th, 2008, 9:12pm » |
Quote Modify
|
Given a grid of n X n squares, what are the number of ways to reach from one end vertex (bottom left) to another top right vertex walking only along edges of squares when
i) you can move only left anf above
ii) you can use any edge only once but can move in any of the 4 directions?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number of ways
« Reply #3 on: Feb 9th, 2008, 10:40pm » |
Quote Modify
|
on Feb 9th, 2008, 9:12pm, mad wrote:Given a grid of n X n squares, what are the number of ways to reach from one end vertex (bottom left) to another top right vertex walking only along edges of squares when
i) you can move only left anf above |
|
There must be 2n moves; you can choose n of them to be right, and the other n to be up, in C(2n,n) ways.
Quote:| ii) you can use any edge only once but can move in any of the 4 directions? |
|
A lot. Over a billion just for a 5x5 grid!
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Number of ways
« Reply #4 on: Feb 9th, 2008, 11:50pm » |
Quote Modify
|
But, can't any formula be derived? I mean since we can use any edge only once, there must be an upper bound.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number of ways
« Reply #5 on: Feb 10th, 2008, 7:14am » |
Quote Modify
|
on Feb 9th, 2008, 11:50pm, mad wrote:| But, can't any formula be derived? I mean since we can use any edge only once, there must be an upper bound. |
|
Well, it won't go beyond (n*n)!, but that's not a very tight upper bound.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Number of ways
« Reply #6 on: Feb 10th, 2008, 9:34am » |
Quote Modify
|
3^((N-2)^2)*2^(4(N-2))*2 is a bit tighter bound.
(I hope it's correct  )
|
| « Last Edit: Feb 10th, 2008, 9:35am by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print