Answer to the November 29, 2004 Problem of the Week

The Pleacher Family Travel Problem

• Home
• Meet Mr. P
• What's New
• Humor
• Lesson Plans
• Quotes
• Links
• Puzzles & Games
• Problem of the Month
• Math Facts
• Logic Puzzles

Mr. Pleacher and his wife want to take a trip to visit his brother, his parents, and each of their children.
Mr. Pleacher and his wife live in Stephens City, VA. (SC on the map below)
Mr. Pleacher's brother lives in Leitchfield, KY. (L on the map)
Mr. Pleacher's parents live in Owensboro, KY. (O on the map)
Mr. Pleacher's daughter Elizabeth and her family live in Ponte Vedra Beach, FL. (PVB on the map)
Mr. Pleacher's daughter Sarah and her family live in Fort Collins, CO. (FC on the map)
Mr. Pleacher's son Michael and his wife live in Portland, ME. (P on the map)

The distances between the cities are given below:

• Stephens City to Portland is 615 miles
• Stephens City to Ponte Vedra Beach is 758 miles
• Stephens City to Fort Collins 1,639 miles
• Stephens City to Leitchfield is 588 miles
• Stephens City to Owensboro 651 miles
• Owensboro to Ponte Vedra Beach is 744 miles
• Owensboro to Fort Collins is 1,111 miles
• Owensboro to Leitchfield is 65 miles
• Owensboro to Portland is 1,188 miles
• Ponte Vedra Beach to Portland is 1,280 miles
• Ponte Vedra Beach to Fort Collins is 1,824 miles
• Portland to Fort Collins is 2,070 miles

Using the data above, help Mr. Pleacher and his wife plan a roundtrip to visit each relative without passing through any city more than once (except the return home to Stephens City).
You may use only the routes indicated on the map -- there is only one road into Leitchfield and one road out (you must go through Stephens City or Owensboro to get there).
Find the shortest path.

 

---

Solution to the Problem:

The shortest paths are:
SC - P - PVB - FC - O - L - SC
and its reverse
SC - L - O - FC - PVB - P - SC, which are both 5,483 miles.

I used a tree diagram to examine all possible paths. Then I set up a table to find the shortest path(s).

SC	-	P	-	FC	-	PVB	-	O	-	L	-	SC	=	5,906 miles
SC	-	P	-	PVB	-	FC	-	O	-	L	-	SC	=	5,483 miles
SC	-	L	-	O	-	PVB	-	P	-	FC	-	SC	=	6,386 miles
SC	-	L	-	O	-	PVB	-	FC	-	P	-	SC	=	5,906 miles
SC	-	L	-	O	-	P	-	PVB	-	FC	-	SC	=	6,584 miles
SC	-	L	-	O	-	P	-	FC	-	PVB	-	SC	=	6,493 miles
SC	-	L	-	O	-	FC	-	P	-	PVB	-	SC	=	5,872 miles
SC	-	L	-	O	-	FC	-	PVB	-	P	-	SC	=	5,483 miles
SC	-	PVB	-	P	-	FC	-	O	-	L	-	SC	=	5,872 miles
SC	-	PVB	-	FC	-	P	-	O	-	L	-	SC	=	6,493 miles
SC	-	FC	-	P	-	PVB	-	O	-	L	-	SC	=	6,386 miles
SC	-	FC	-	PVB	-	P	-	O	-	L	-	SC	=	6,584 miles

So, paths #2 and #8 above have the least mileage of 5,483 miles, a savings of 1,101 miles over routes #5 or 12.

Correctly solved by: