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!

Pathway Problem

  1. May 14, 2008 #1
    1. The problem statement, all variables and given/known data
    A taxi company is trying to find the quickest route during rush hour traffic from the train station to the football stadium. How many different routes must be considered if at each intersection the taxi must always move closer to the football stadium?

    [​IMG]


    2. Relevant equations
    [tex]n_{P}_r=\frac{n!}{(n-r)!}[/tex]


    3. The attempt at a solution
    My teacher told us that he didn't know how to solve this problem using permutations, and therefore solved it using pascal's triangle. This is what he did:
    [​IMG]
    As you see, he got the answer of 119, which is correct. However, I was wondering, is there a way of doing this question using the permutations equation? If not, is there another way of approaching this problem?
     
  2. jcsd
  3. May 14, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    There's a lot of ways to do the problem by splitting it into a bewildering variety of cases and subcases. Your teachers solution is probably the best. In fact it's actually really nice. I might have tried to do it a harder way.
     
  4. May 14, 2008 #3
    Could you show me how you would have solved this using the perms. formula?
     
  5. May 14, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    There is no way to solve it using the permutations formula with a single n and r. I.e. there is not an easy way to solve it using a fixed formula. That's why your teachers solution is good. Why do you want to solve it with the 'perms' formula?
     
  6. May 15, 2008 #5
    Well now that you have said that, I guess I will stick with my teacher's solution. It's just that I like having algebraic work backing up a solution when there can be one. I did not initially think it would be so difficult to solve this problem using the formula, as it is quite simple.
     
  7. May 15, 2008 #6
    The reason why it is difficult with a formula is because not every intersection has an equal number of possible moves. That's why other ways to do it involve cases and subcases.
     
  8. May 15, 2008 #7
    It's not that difficult. If the map was a complete 4x5 rectangle there would be 9C4 = 9!/(4!5!) = 126 paths. Only one path goes through the upper left point, and 6C1 = 6 paths going through the point 3 left of the football stadium.
    The total number is 9C4 - 1 - 6C1 = 119
     
  9. May 15, 2008 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Very clever.
     
  10. May 15, 2008 #9
    Thanks for the help kamerling.

    I also realized that you could do [tex]126-2!-(\frac{3!}{2!}+2!)=119[/tex]
    There are [tex]2![/tex] ways of getting through the top right box, and there are [tex](\frac{3!}{2!}+2!)[/tex] of getting through the two bottom left boxes. Therefore, you just subtract these seven ways from the total, 126, to get 119.

    See Dick, it's not that difficult.:approve:
     
  11. May 15, 2008 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Point taken.
     
  12. May 15, 2008 #11
    I don't understand this. What are the 2 ways of getting through top right box? There's only one path there that shouldn't be counted.
     
  13. May 15, 2008 #12
    Sorry if I confused you. What I meant to say is if there was a box in the top right corner, there would be two ways of getting from point A to point B, as shown below. As you can see, there is a red and blue path.

    [​IMG]
     
  14. May 15, 2008 #13
    Sorry, I see that this works, and I had thought about completing the map before, but I couldn't quite get to the 9C4. Can someone quickly explain to me how it works?
     
  15. May 15, 2008 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You have 9 turns to make during the trip, any one can be to the left or down. To get to the destination you need to make 4 left turns and 5 down turns. How many ways?
     
  16. May 15, 2008 #15
    119 = 6!/3! - 1 ;)
     
  17. May 15, 2008 #16
    Ah, I see. That's pretty nice :)
     
  18. May 16, 2008 #17
    Does this mean that if you had a rectangle where only the top right corner was missing, you'd say that there were 126 - 2! = 124 paths? That answer is wrong.
     
  19. May 16, 2008 #18
    What I should have drawn is this:

    [​IMG]

    This is because what I previously had as the blue path, is accessible with or without the top right square being there. Therefore, it would be 126-1=125, which, I believe, is the right answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Pathway Problem
  1. Pathway problem (Replies: 2)

  2. Pathway problem (Replies: 1)

Loading...