anonymous
  • anonymous
The streets of a city are arranged like the lines of a chess-board. Let the dimensions be \(m \times n\). Find the number of ways in which a man can travel from the North-West corner to the South-East corner, going the shortest possible distance.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
jamiebookeater
  • jamiebookeater
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
karatechopper
  • karatechopper
thts a lot of turns i can take x(
experimentX
  • experimentX
Kinda sounds like problem asked by FFM
karatechopper
  • karatechopper
who know when i could get lost :/ @Diyadiya will drive me! then no need to worry!

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
It is similar to FFM's problem.
experimentX
  • experimentX
then it must be related to this http://en.wikipedia.org/wiki/Motzkin_number
experimentX
  • experimentX
n+1th Mozkin's no
karatechopper
  • karatechopper
@Ishaan94 i have an answer
karatechopper
  • karatechopper
o wait not yet!
experimentX
  • experimentX
|dw:1339345895603:dw| seems to be six int this case
Zarkon
  • Zarkon
yes...six..\({4\choose 2}\)
Zarkon
  • Zarkon
maybe I should write it \[{2+2\choose 2}\]
experimentX
  • experimentX
|dw:1339346361572:dw|
experimentX
  • experimentX
|dw:1339346637952:dw|
experimentX
  • experimentX
so for 2x3 ...we have 10
Zarkon
  • Zarkon
\[{5 \choose 2}\]
experimentX
  • experimentX
so adding one segments ... \[ \binom {4 + 1}{2}\]
Zarkon
  • Zarkon
\[{3+2\choose 2}\]
experimentX
  • experimentX
|dw:1339346850772:dw|
Zarkon
  • Zarkon
for your 3x2 you will have to go 3 units up and 2 units to the right in total to get to the upper right hand corner UUURR the number of ways to arrange these letters is \({3+2\choose 2}\)
experimentX
  • experimentX
|dw:1339346924974:dw|
experimentX
  • experimentX
2*4+2*10+6*3 = \( \binom{9}{2} = \binom{3 + 3 + 3}{2}\)
Zarkon
  • Zarkon
there are only 20 ways for a 3x3
Zarkon
  • Zarkon
\[{m+n\choose n}\]
anonymous
  • anonymous
Yeah, because you take m+n steps and you must decide which n of them will be right, or which m of them will be down (it's equivalent).
Zarkon
  • Zarkon
yes
experimentX
  • experimentX
isn't there 36 steps in 3x3??
Zarkon
  • Zarkon
show me a path that requires 36 steps
experimentX
  • experimentX
something wrong with draw app here ... can't copy my own drawing!!
Zarkon
  • Zarkon
only 6 steps are needed to get to the bottom right
experimentX
  • experimentX
|dw:1339348259654:dw|
Zarkon
  • Zarkon
there are 6 ways to do a 2x2 not 10
experimentX
  • experimentX
Oh .. i made mistake then ... it must be 3x2
experimentX
  • experimentX
|dw:1339348688431:dw|
Zarkon
  • Zarkon
yes
experimentX
  • experimentX
shouldn't it be 2*3*3+2*4+2*6 = 38 ??
Zarkon
  • Zarkon
try and draw 38 minimum distance paths using that graph
anonymous
  • anonymous
I'm getting ( m + n -2)!/(m-1)!(n-1)! ??????
anonymous
  • anonymous
|dw:1339384651187:dw|
anonymous
  • anonymous
Let each square formed be a unit square. Therefore if a man needs to get from NW to south east, He basically needs to cover "n-1" units on the east line. And "m-1" units south. --- For the Shortest possible path when he decides to never turn back. Now in order to do this each street taken by him must be in the South or east direction. Every time he goes east Lets call that turn/ street taken E. Every time he turns south we call that S. So any path followed by him can be written as: SSESESESSSSEEE........... ----- Meaning the man goes first south then south again without turning at next intersection Then turns east at the next turn.......... Here number of S's = m-1 No. of E's = n-1. So the problem has become an equivilant of Finding the permutations of n-1 E's and m-1 S's. = ( m -1 + n -1)! ----------------- (m-1)!(n-1)!
Zarkon
  • Zarkon
|dw:1339422624581:dw| this is a 1x1 block so m=1 and n=1 using your formula \[\frac{(1-1+1-1)}{(1-1)!(1-1)!}=\frac{0!}{0!0!}=1\] but there are 2 paths to the end
anonymous
  • anonymous
My formula deals with streets. => lines. => m = 2, n=2 in this caase
Zarkon
  • Zarkon
mine does not
Zarkon
  • Zarkon
I go by the number of blocks created and the number of steps to go from one corner to the other for a 1x1 block you have to go down 1 and to the right 1
experimentX
  • experimentX
should have never doubted @Zarkon http://math.stackexchange.com/questions/103470/how-can-i-find-the-number-of-the-shortest-paths-between-two-points-on-a-2d-latti

Looking for something else?

Not the answer you are looking for? Search for more explanations.