Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Ishaan94

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.

  • one year ago
  • one year ago

  • This Question is Closed
  1. karatechopper
    Best Response
    You've already chosen the best response.
    Medals 0

    thts a lot of turns i can take x(

    • one year ago
  2. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    Kinda sounds like problem asked by FFM

    • one year ago
  3. karatechopper
    Best Response
    You've already chosen the best response.
    Medals 0

    who know when i could get lost :/ @Diyadiya will drive me! then no need to worry!

    • one year ago
  4. Ishaan94
    Best Response
    You've already chosen the best response.
    Medals 0

    It is similar to FFM's problem.

    • one year ago
  5. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    then it must be related to this http://en.wikipedia.org/wiki/Motzkin_number

    • one year ago
  6. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    n+1th Mozkin's no

    • one year ago
  7. karatechopper
    Best Response
    You've already chosen the best response.
    Medals 0

    @Ishaan94 i have an answer

    • one year ago
  8. karatechopper
    Best Response
    You've already chosen the best response.
    Medals 0

    o wait not yet!

    • one year ago
  9. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339345895603:dw| seems to be six int this case

    • one year ago
  10. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    yes...six..\({4\choose 2}\)

    • one year ago
  11. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    maybe I should write it \[{2+2\choose 2}\]

    • one year ago
  12. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339346361572:dw|

    • one year ago
  13. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339346637952:dw|

    • one year ago
  14. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    so for 2x3 ...we have 10

    • one year ago
  15. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    \[{5 \choose 2}\]

    • one year ago
  16. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    so adding one segments ... \[ \binom {4 + 1}{2}\]

    • one year ago
  17. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    \[{3+2\choose 2}\]

    • one year ago
  18. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339346850772:dw|

    • one year ago
  19. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    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}\)

    • one year ago
  20. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339346924974:dw|

    • one year ago
  21. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    2*4+2*10+6*3 = \( \binom{9}{2} = \binom{3 + 3 + 3}{2}\)

    • one year ago
  22. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    there are only 20 ways for a 3x3

    • one year ago
  23. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    \[{m+n\choose n}\]

    • one year ago
  24. goxenul
    Best Response
    You've already chosen the best response.
    Medals 0

    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).

    • one year ago
  25. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    yes

    • one year ago
  26. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    isn't there 36 steps in 3x3??

    • one year ago
  27. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    show me a path that requires 36 steps

    • one year ago
  28. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    something wrong with draw app here ... can't copy my own drawing!!

    • one year ago
  29. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    only 6 steps are needed to get to the bottom right

    • one year ago
  30. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339348259654:dw|

    • one year ago
  31. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    there are 6 ways to do a 2x2 not 10

    • one year ago
  32. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    Oh .. i made mistake then ... it must be 3x2

    • one year ago
  33. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339348688431:dw|

    • one year ago
  34. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    yes

    • one year ago
  35. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    shouldn't it be 2*3*3+2*4+2*6 = 38 ??

    • one year ago
  36. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    try and draw 38 minimum distance paths using that graph

    • one year ago
  37. siddhantsharan
    Best Response
    You've already chosen the best response.
    Medals 1

    I'm getting ( m + n -2)!/(m-1)!(n-1)! ??????

    • one year ago
  38. siddhantsharan
    Best Response
    You've already chosen the best response.
    Medals 1

    |dw:1339384651187:dw|

    • one year ago
  39. siddhantsharan
    Best Response
    You've already chosen the best response.
    Medals 1

    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)!

    • one year ago
  40. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    |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

    • one year ago
  41. siddhantsharan
    Best Response
    You've already chosen the best response.
    Medals 1

    My formula deals with streets. => lines. => m = 2, n=2 in this caase

    • one year ago
  42. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    mine does not

    • one year ago
  43. Zarkon
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • one year ago
  44. experimentX
    Best Response
    You've already chosen the best response.
    Medals 1

    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

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.