Optimal Itinerary Planning for a Business Trip to Six Major Cities

[DotKite]

Homework Statement

A businesswoman in Philadelphia is preparing an itinerary for a visit to six major cities. The distance traveled, and hence the cost of the trip, will depend on the order in which she plans the route.

a) how many different itineraries ( and trip costs) are possible)?

Since order is significant I used the equation for permutations and arrived at an answer of 720 possible itineraries. (I hope this much is correct)

b) If the business woman selects one of the possible itineraries and Denver and San Francisco are two of the cities she plans to visit, what is the probability she will visit Denver before San Francisco?

Homework Equations

The Attempt at a Solution

OK I am just terrible at this stuff. I never know how to count anything. I go over and over on the principles of counting, but I fail to be able to apply them. part a I understand. It is 6!. However part b just immediately confuses me.

So you want all possibilities that denver is before san fran.

D F _ _ _ _
_ D F _ _ _
_ _D F _ _
_ _ _ D F _
_ _ _ _ D F

For each of these "possibilities" there are still 4 cities to be ordered. So for each of those listed there are 4! different ways to arrange each one of them? here is where i get stuck

 

[Simon Bridge]

She visits each one only once, and the order matters ... so there are
She has 6 choices of first city, then one of the remaining 5 for the second and so on... for a total of 6x5x4x3x2x1=720 possible itineraries. Well done.

It is usually easier to think of it this way that to remember the equations.

part (b)
Cities may be A,B,C,D,E,F ... for 6 cities.
D=Denver, F=San Francisco.

Maybe the others are Abeline, Beaumont, Charleston, and Elgin ... whatever right?
But we can use X for a dummy city: x is one of {A,B,D,E} so there's four cities left.

To help you think about it: there are six slots on the itinerary:
Once you have place a D in one slot - there are five available slots remaining for F.
But some of those slots come before the D.

DFXXXX does this, but so will DXFXXX

But if you really just need to know how many instances there are where F appears right after D - you just put them in a bag (DF) and treat them as a single destination.

if other cities can be between them ... then there will be more possibilities.
i.e. you can put (FXD) in a bag - note: there's four possible bags.

 

[haruspex]

a) how many different itineraries ( and trip costs) are possible)?

That's a bit glib. Assuming each city-city hop costs the same in each direction, the number of itineraries is at least twice the number of trip costs.

For b), I'm not sure you're expected to work through all these possibilities. Is there any reason why visiting Denver before SF is more or less likely than the other way around?