Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Ishaan94

  • 2 years ago

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.

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

    thts a lot of turns i can take x(

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

    Kinda sounds like problem asked by FFM

  3. karatechopper
    • 2 years ago
    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!

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

    It is similar to FFM's problem.

  5. experimentX
    • 2 years ago
    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

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

    n+1th Mozkin's no

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

    @Ishaan94 i have an answer

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

    o wait not yet!

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

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

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

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

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

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

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

    |dw:1339346361572:dw|

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

    |dw:1339346637952:dw|

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

    so for 2x3 ...we have 10

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

    \[{5 \choose 2}\]

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

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

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

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

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

    |dw:1339346850772:dw|

  19. Zarkon
    • 2 years ago
    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}\)

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

    |dw:1339346924974:dw|

  21. experimentX
    • 2 years ago
    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}\)

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

    there are only 20 ways for a 3x3

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

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

  24. goxenul
    • 2 years ago
    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).

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

    yes

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

    isn't there 36 steps in 3x3??

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

    show me a path that requires 36 steps

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

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

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

    only 6 steps are needed to get to the bottom right

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

    |dw:1339348259654:dw|

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

    there are 6 ways to do a 2x2 not 10

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

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

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

    |dw:1339348688431:dw|

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

    yes

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

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

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

    try and draw 38 minimum distance paths using that graph

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

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

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

    |dw:1339384651187:dw|

  39. siddhantsharan
    • 2 years ago
    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)!

  40. Zarkon
    • 2 years ago
    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

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

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

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

    mine does not

  43. Zarkon
    • 2 years ago
    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

  44. experimentX
    • 2 years ago
    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

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

    • Attachments:

Ask your own question

Ask a Question
Find more explanations on OpenStudy

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.