Answer to Problem of the Week for 01/23/2006

Answer to the Problem of the Week for the week of January 23, 2006

Pentagon Island

Pentagon Island has one airport located in the town of Winchester. A railroad links the five cities on the island -- Winchester, Bennettsville, Columbus, Flint, and Ventura. The track forms a complete loop, and trains run in both directions (see the diagram below).

When you land at the airport in Winchester, you are given a free pass, for eight trips on the train, between one town and the next. In how many different ways can you make a trip of exactly eight trips, starting and ending in Winchester?

If you are thinking that it is impossible to use all 8 tickets -- here is one possible trip: W - B - W - B - W - B - W - B - W.

Solution to the Problem:

The answer is 70 different trips!

To solve this problem, I drew a tree diagram. I started with W on one end. There are only two cities that can be reached directly from W -- they are B and V. Then from B, you can go to W or C. I continued this for the top half of the tree and then I could see by symmetry that there would be double that number.

Here are the thirty-five 8-city trips in the top half of the tree:

W-B-W-B-W-B-W-B-W
W-B-W-B-W-B-W-V-W
W-B-W-B-W-B-C-B-W
W-B-W-B-W-V-W-B-W
W-B-W-B-W-V-W-V-W
W-B-W-B-W-V-F-V-W

W-B-W-B-C-B-W-B-W
W-B-W-B-C-B-W-V-W
W-B-W-B-C-B-C-B-W
W-B-W-B-C-F-C-B-W

W-B-W-V-W-B-W-B-W
W-B-W-V-W-B-W-V-W
W-B-W-V-W-B-C-B-W
W-B-W-V-W-V-W-B-W
W-B-W-V-W-V-W-V-W
W-B-W-V-W-V-F-V-W

W-B-W-V-F-C-F-V-W
W-B-W-V-F-V-W-V-W
W-B-W-V-F-V-W-B-W
W-B-W-V-F-V-F-V-W

W-B-C-B-W-B-W-B-W
W-B-C-B-W-B-W-V-W
W-B-C-B-W-B-C-B-W
W-B-C-B-W-V-W-B-W
W-B-C-B-W-V-W-V-W
W-B-C-B-W-V-F-V-W

W-B-C-B-C-B-W-B-W
W-B-C-B-C-B-W-V-W
W-B-C-B-C-B-C-B-W
W-B-C-B-C-F-C-B-W

W-B-C-F-C-B-W-B-W
W-B-C-F-C-B-W-V-W
W-B-C-F-C-B-C-B-W
W-B-C-F-C-F-C-B-W
W-B-C-F-V-F-C-B-W

Here are the thirty-five 8-city trips in the bottom half of the tree:

w-v-f-c-b-c-f-v-w
w-v-f-c-f-c-f-v-w
w-v-f-c-f-v-f-v-w
w-v-f-c-f-v-w-b-w
w-v-f-c-f-v-w-v-w
w-v-f-v-f-c-f-v-w
w-v-f-v-f-v-f-v-w
w-v-f-v-f-v-w-b-w
w-v-f-v-f-v-w-v-w
w-v-f-v-w-b-c-b-w
w-v-f-v-w-b-w-b-w
w-v-f-v-w-b-w-v-w
w-v-f-v-w-v-f-v-w
w-v-f-v-w-v-w-b-w
w-v-f-v-w-v-w-v-w
w-v-w-b-c-b-c-b-w
w-v-w-b-c-b-w-b-w
w-v-w-b-c-b-w-v-w
w-v-w-b-c-f-c-b-w
w-v-w-b-w-b-c-b-w
w-v-w-b-w-b-w-b-w
w-v-w-b-w-b-w-v-w
w-v-w-b-w-v-f-v-w
w-v-w-b-w-v-w-b-w
w-v-w-b-w-v-w-v-w
w-v-w-v-f-c-f-v-w
w-v-w-v-f-v-f-v-w
w-v-w-v-f-v-w-b-w
w-v-w-v-f-v-w-v-w
w-v-w-v-w-b-c-b-w
w-v-w-v-w-b-w-b-w
w-v-w-v-w-b-w-v-w
w-v-w-v-w-v-f-v-w
w-v-w-v-w-v-w-b-w
w-v-w-v-w-v-w-v-w

Correctly solved by:

1. Evelyne Stalzer	Montville, New Jersey
2. James Alarie	University of Michigan -- Flint Flint, Michigan
3. David & Judy Dixon	Bennettsville, South Carolina
4. Jeffrey Gaither	University of Virginia Charlottesville, Virginia

Honorable Mention goes to Ana Gonzalez of Winchester, Virginia whose answer was very close. She sent in an enumerated list similar to that above.