Finding the Quickest Route During Rush Hour Traffic

[temaire]

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?

 

[Dick]

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.

 

[temaire]

Could you show me how you would have solved this using the perms. formula?

 

[Dick]

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?

 

[temaire]

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.

 

[Tedjn]

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.

 

[kamerling]

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

 

[Dick]

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.

 

[temaire]

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.

 

[Dick]

See Dick, it's not that difficult.

Point taken.

 

[kamerling]

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.

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.

 

[temaire]

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]

 

[Tedjn]

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?

 

[Dick]

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?

 

[BrendanH]

119 = 6!/3! - 1 ;)

 

[Tedjn]

Ah, I see. That's pretty nice :)

 

[kamerling]

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.

 

[temaire]

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.