Finding the Quickest Route During Rush Hour Traffic

  • Thread starter Thread starter temaire
  • Start date Start date
Click For Summary
SUMMARY

The forum discussion centers on calculating the number of distinct routes a taxi can take from a train station to a football stadium during rush hour traffic, specifically when the taxi must always move closer to the destination. The correct solution, derived using combinatorial methods, indicates that there are 119 valid routes. This was confirmed through the use of combinations, specifically 9C4, which accounts for the necessary left and down moves. The discussion also highlights the complexity of using permutations due to varying intersection options.

PREREQUISITES
  • Understanding of combinatorial mathematics, specifically combinations and permutations.
  • Familiarity with Pascal's Triangle and its application in combinatorial problems.
  • Basic knowledge of grid-based pathfinding and movement constraints.
  • Ability to interpret and manipulate factorial expressions in mathematical equations.
NEXT STEPS
  • Study combinatorial pathfinding techniques in grid layouts.
  • Learn about advanced applications of Pascal's Triangle in combinatorial problems.
  • Explore the differences between permutations and combinations in depth.
  • Investigate real-world applications of combinatorial mathematics in logistics and routing.
USEFUL FOR

Mathematicians, educators, students studying combinatorics, and professionals in logistics or transportation planning who are interested in optimizing route calculations.

temaire
Messages
275
Reaction score
0

Homework Statement


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?

http://img179.imageshack.us/img179/4730/pathwayjh2.png​
[/URL]


Homework Equations


n_{P}_r=\frac{n!}{(n-r)!}


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:
http://img81.imageshack.us/img81/162/pathway2oh6.png​
[/URL]
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?
 
Last edited by a moderator:
Physics news on Phys.org
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.
 
Could you show me how you would have solved this using the perms. formula?
 
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?
 
Dick said:
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.

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.
 
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.
 
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
 
kamerling said:
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

Very clever.
 
Thanks for the help kamerling.

I also realized that you could do 126-2!-(\frac{3!}{2!}+2!)=119
There are 2! ways of getting through the top right box, and there are (\frac{3!}{2!}+2!) 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:
 
  • #10
temaire said:
See Dick, it's not that difficult.:approve:

Point taken.
 
  • #11
temaire said:
Thanks for the help kamerling.

I also realized that you could do 126-2!-(\frac{3!}{2!}+2!)=119
There are 2! ways of getting through the top right box, and there are (\frac{3!}{2!}+2!) 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:

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.
 
  • #12
kamerling said:
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.

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.

http://img234.imageshack.us/img234/8017/pathway3nv0.png​
[/URL]
 
Last edited by a moderator:
  • #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?
 
  • #14
Tedjn said:
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?

You have 9 turns to make during the trip, anyone 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?
 
  • #15
119 = 6!/3! - 1 ;)
 
  • #16
Ah, I see. That's pretty nice :)
 
  • #17
temaire said:
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.

http://img234.imageshack.us/img234/8017/pathway3nv0.png​
[/URL]

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.
 
Last edited by a moderator:
  • #18
What I should have drawn is this:

http://img223.imageshack.us/img223/9485/pathway3jq9.png​
[/URL]

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.
 
Last edited by a moderator:

Similar threads

Car Crash and Such: Investigation and Analysis
  • · Replies 33 ·
2
Replies
33
Views
14K