1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Routes through a 2D grid.

  1. Nov 17, 2013 #1
    Hi all.

    I have a grid with 4 points, A, B, C, and D.
    Each valid move is either going to the right for one block or going down for 1 block.

    Here is the grid.

    I need to calculate the following:
    a) How many different valid routes from A to D?
    b) How many valid routes from A to D that must avoid B?
    c) How many valid routes from A to D that must pass through Both B and C?
    d) How many valid routes from A to D that must pass through B but must avoid C ?

    I believe for A, I would calculate 13 choose 9 to obtain 715 possible routes.

    Where I am confused is how I calculate in the avoidance and musts. For example, on b, if I wanted to avoid B, would I treat A to be like a mini 4x5 sub-grid? Would I subtract 4 choose 4 from 715 to obtain 710 possible routes?

    Any help is appreciated. I can't seem to find any information on this in my book :(.
     
  2. jcsd
  3. Nov 17, 2013 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That isn't correct for A. It is going to take ##13+9=22## steps to get from A to D. Each step is either r or d for "right" or "down". So think of 22 blank spaces that are going to be either r or d depending whether that step is right or down. You have to choose which slots correspond to the 13 down steps. How many ways can you do that? Alternatively, how many ways can you choose which slots are move right? That might get you started.
     
  4. Nov 17, 2013 #3
    Right. But the question is how many valid routes there are, not how many steps.

    The other method I saw to count this would be (9+13)! / 9!13! which equals 497,420. I have no idea if it's 715 or 497,420.
     
  5. Nov 17, 2013 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You need to give a bit more thought to what I said. If I tell you exactly which steps will be down, does that completely determine a route?
     
  6. Nov 17, 2013 #5
    Unfortunately it doesn't make any sense to me.

    What do you mean by "choose which slots correspond to the 13 down steps"? How do I go about "choosing" that?

    If there are 13 down steps, and 9 right steps, I suppose that there are 13x9 choices? I really have no idea, sorry.
     
  7. Nov 17, 2013 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Do you see that you have to take 22 steps to get from A to D? And that 13 of them have to be down? And that once you pick which of the 22 steps are down, the rest have to be to the right? So that once you know which steps are to be down, there is only 1 path that does that?
     
  8. Nov 17, 2013 #7
    Yes, I do see that, but I don't understand how that helps me count the total number of routes. If I choose a route by hand, that's just 1 route. There has to be some kind of formula, otherwise I'd be here for a week calculating routes.
     
  9. Nov 17, 2013 #8

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Here's one route:

    dddddddddddddrrrrrrrrr

    If I put the d's in different spots will that give me a different route?
     
  10. Nov 17, 2013 #9
    I took some time to relax and I've come back to the problem now.
    So if we look at having 13 moves down, and 9 moves right, then we can get the combinations using 13C9.

    a) 13C9 = 715 possible routes.

    b)
    If we want to avoid B, we should find out how many moves from A to B.
    5C4 = 5, and 715 -5 = 710. So there are 710 possible routes while avoiding B.

    c) For the routes which must pass through B and C, we look at the number of steps to reach B, and the number of steps to reach C, and then the number of steps to reach D from C.
    So we get
    5C4 + 7C9 + 9C5 = 138 possible routes.

    Am I on the right track now?
     
  11. Nov 17, 2013 #10

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. I told you that was wrong with my first post. And you ignored my last post, which I re-quoted above. I'm trying to lead you to discover how to do it. Answer the above question.
     
  12. Nov 17, 2013 #11
    I'm not ignoring anything. I honestly don't understand.

    I'm trying. Yes. If you put d's in the different spots you will get a different route.

    I think my nCk is incorrect. So if we have 22 moves, and I want to see how many down moves I have, I would choose 13 from 22, so 13C22, which is 497,420 paths. Is this on the right track?
     
  13. Nov 18, 2013 #12
    When I calculate the routes from A to B, I do it with 9choose5, which equals 125. This is the same formula for 22choose13 which yields 497,420 from A to D.

    497,420 - 3128 = 491,254 routes avoiding B.

    For c, the valid routes from A to D that must pass through both B and C, I just add the routes up.

    9choose5 + 9choose6 + 8choose5 = 125+84+56 = 265 routes.

    For d, the valid routes from A to D which pass through B but avoid C, I add the routes from A to B (125), subtract the routes from B to C (84), and add the routes from B to D (3128).
    125-84+3128 = 3169 routes.

    I think I'm getting there, slowly?
     
  14. Nov 18, 2013 #13

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That isn't "how many down moves you have". It is how many ways you can choose which moves to be down. ##_{22}C_{13} = 497420## is correct. Do you understand my first post now?
     
  15. Nov 18, 2013 #14
    I do. Thanks. I am going to go over the other problems again tonight.

    I would assume I can treat the area from A to B, or B to C as a "sub-grid" and calculate the choices within those sub-grids.

    Thanks again.
     
  16. Nov 18, 2013 #15

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Wrong numbers for A to B. Look again.

    Very slowly. Pretty much all wrong. You have (a) correct, now let's get (b) correct. On part at a time. To answer (b) you need to know how many routes from A to D go through B so you can leave them out. How can you calculate that?
     
  17. Nov 18, 2013 #16
    To calculate the number of routes that go through B. I believe I want to determine how many moves I need to make down and right to get from A to B.

    To get from A to B, I see I need to go down 3 at some point, and right 5 at some point. So there are 8choose3 (or 56) routes from A to B.

    So would I remove 56 from 497420?
     
  18. Nov 18, 2013 #17

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Wrong numbers. Look at your grid again. Second time I've pointed that out to you.

    No. Read my re-quoted post again.
     
  19. Nov 18, 2013 #18
    You said "It is how many ways you can choose which moves to be down. 22C13=497420 is correct." Above. I'm not sure why you're saying that's wrong now?

    Can you throw me a bone here man instead of just saying "wrong wrong wrong"? It's not helping. Trust me. I read your posts over and over agian.

    The B is in the upper left hand corner of the grid. It is 3 down, and 5 right. No?
     
  20. Nov 18, 2013 #19

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Maybe we are looking at different pictures? If you start at the upper left corner it is 3 steps down and 4 steps right to get to corner B isn't it?
     
  21. Nov 18, 2013 #20
    Yes. Ok I see now. It is 3 down and 4 right.

    So is it correct to say 7choose3, and the result is 35? If so, I will take some time to try and re-work the rest of the problems.

    Thanks agian.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Routes through a 2D grid.
  1. Grid Curve stuff Help! (Replies: 2)

  2. Grid Curves (Replies: 10)

Loading...