1. Not finding help here? Sign up for a free 30min 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!

Paths in a grid

  1. Dec 26, 2015 #1
    1. The problem statement, all variables and given/known data
    In a grid O(0,0) A(7,8) find the number of paths that
    1. pass through (3,4)
    2. don't pass through (3,4)
    3. pass through M(2,3) AND N(4,6)
    4. DON'T pass pass through M(2,3) and N(4,6)
    5. pass through ONLY ONE of M(2,3) and N(4,6)
    6. pass through AT LEAST ONE of M(2,3) and N(4,6)
    7. pass through M(2,3) and don't pass through N(4,6)

    2. Relevant equations
    If the grid starts at O(0,0) and ends at A(7,8) then the length of each path is 7+8=15. The number of paths is C(7+8,7) = C(15,7)

    3. The attempt at a solution
    To find the number of paths that pass through (3,4), I found
    1. the number of paths from O(0,0) to M(3,4) which is C(3+4,3) = C(7,3) = 7*6*5 / 1*2*3 = 35
    2. the number of paths from M(3,4) to A(7,8) which is C(4+4,4) = C(8,4) = 8*7*6*5 / 1*2*3*4 = 70
    3. 35*70=2450

    This one is easy so I figured it out easily, please provide me with some guidance to solve the others too.
     
  2. jcsd
  3. Dec 26, 2015 #2
    To move (0,0) ##\to## (7,8) trough (3,4) you must add all possible ways moving only to "right" and "up".
    Because this condition may possible ways are less than you think.
     
  4. Dec 26, 2015 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Q3 is just more of the same - (0,0) to (2,3), then (2,3) to (4,6) etc.
    For Q2, how many ways are there from (0,0) to (7,8) altogether?
    I believe Lilia has taken that into account already.
     
  5. Dec 27, 2015 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    One hint only: in (2), number of paths from (0,0) to (7,8) NOT passing through (3,4) = total paths from (0,0) to (7,8), minus those that pass through (3,4).
     
  6. Dec 27, 2015 #5
    There are C(7+8,7) = C(15,7) = 15*14*13*12*11*10*9 / 1*2*3*4*5*6*7 = 6435 paths from O(0,0) to A(7,8). If I exclude the number of paths through M(3,4), that'd be number of paths that don't pass through M(3,4), right?

    Q3: C(5,2) * C(5,2) * C(5,2). Isn't there anything to add?

    Q5 and Q7 are similar in a way. In Q5 it says ONLY ONE which is, the path passes through M(2,3) and doesn't pass through N(4,6) OR the path passes through N(4,6) and doesn't pass through M(2,3). Therefore, for Q7

    the number of paths that pass through M(2,3) is C(5,2)*C(10,5),
    don't pass through N(4,6) is C(15,7) - (10,4)*C(5,2) (all minus those passing through N(4,6)),
    multiplication of these results will be the number of paths that pass through M(2,3) and don't pass through N(4,6)

    Edit: the number of paths that pass through (2,3) and don't pass through (4,6) will be the number of paths through (2,3) minus the number of paths through (2,3) AND (4,6)

    This is what I figured out so far. Please tell me where I go wrong.
     
    Last edited: Dec 27, 2015
  7. Dec 27, 2015 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The original post said nothing about only moving "right and up". Why are you adding that condition?
     
  8. Dec 27, 2015 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    True, but the calculation performed there for Q1 appears to assume that anyway, so post #2 is redundant.. Some condition must be applied to make the answer finite.
    Yes.
    Looks right.
    Yes.
     
  9. Dec 28, 2015 #8
    And for Q6 (through AT LEAST one) it will be all paths minus those paths that don't pass trough M(2,3) and N(4,6), i.e.

    C(15,7) - [ C(15,7) - [C(5,2)*C(10,5)+C(9,3)*C(6,2)] + C(5,2)*C(4,1)*C(6,2) ]

    Is this right?
     
  10. Dec 28, 2015 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I'm not following how you get that expression. As a numeric answer (if I've computed yours correctly) I get a little more.
    You might be getting confused between two interpretations of 'and'. English is not great for expressing logical conjunctions. In Q4, 'and' means both. In your rephrasing of Q6 above, it has to mean either.
    I would start with the number that pass through the one point, the number that pass through the other point, then consider how many paths are double counted if I add them.
     
  11. Dec 28, 2015 #10
    So, to get the correct answer, from all the paths I should exclude the number of paths that pass through (2,3), then exclude the number of paths that pass through (4,6), then exclude the number of paths that pass through both of the points?
     
  12. Dec 28, 2015 #11

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Since you have to count the paths that pass through at least one of the points (2,3) and (4,6), you cannot exclude paths that pass through these points.

    As haruspex suggested:
    - get the number of all the paths that pass through (2,3)
    - get the number of all the paths that pass through (4,6)
    If you add these two numbers, you have counted all the paths that you need for Q6. But, again as haruspex wrote, some path have been counted twice. If you can identify these paths and get that number ...
     
  13. Dec 29, 2015 #12
    The number of all the paths that pass through (2,3) + the number of all the paths that pass through (4,6) - the number of all the paths that pass through (2,3) and (4,6), right?
     
  14. Dec 29, 2015 #13

    Samy_A

    User Avatar
    Science Advisor
    Homework Helper

    Yes, that is what I meant. That should give the answer to Q6.
     
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: Paths in a grid
  1. Equation of path (Replies: 4)

  2. Helical path (Replies: 1)

Loading...