The Longest Route: Graph Theory and Route Optimisation
#Presented by Manika Gupta
Introduction
#In this puzzle, we have to deliver letters to houses along a street which are on a line. They are all equidistant from each other. But, the path to the houses is very scenic and we want to enjoy it. So, we want to take the longest possible route. We can’t wander aimlessly and can only go from one house to the other and we cannot repeat houses. We can start from any house we want. In what order should we make the deliveries?
This puzzle is adapted from Mathematical Puzzles, Revised Edition by Peter Winkler and Chris Maslanka and Steve Tribe, The Official Sherlock Puzzle Book, Woodland Books, Salt Lake City UT, 2018. ISBN 978-1-4521-7314-6.
Further Questions
- What if there were 10, 12, 20 or any even number of houses? Does this solution generalize?
- What of there were odd number of houses?
- What if the houses were in a line but not equidistant?
Precautions
#Handle the push-pins carefully to avoid injury. Keep the cardboard model flat on the table so that the string lies consistently against it when comparing route lengths.
Materials Required
#A cardboard model of a village (houses, a road, and a green base) Coloured push-pins to mark the stops on the route A length of white string to trace and compare routes
Solution
#Let the houses be labelled A, B, C, D, E, F, G, H. Our path is made of some combination of the paths AB, BC, CD, DE, EF, and GH. We start from one house and have 7 houses left to deliver mail to. So, we can only take 7 trips from house to house in total. How many times can we travel the path AB? At most twice, once on our way to A and once back. The same goes for GH. How about BC? We might be able to do this four times: To A and back (but not from B), and to B and back (not from A). Continuing this reasoning, we see that an upper bound for our longest route is 2AB + 4BC + 6CD + 8DE +6EF + 4F G + 2GH. But we can only take 7 trips in total, so we cannot travel DE 8 times, thus, a better upper bound is 2AB + 4BC + 6CD + 7DE +6EF + 4F G + 2GH.
Is this distance from a possible longest route? If we begin at D or E and end at the other one, after zigzagging between low-numbered houses (A, B, C, D) and high (E, F, G, H). Example: D, H, C, G, B, F, A, E. Find other routes that work!
