Most Ridiculous Routes
A postman with time to spare, made a point of finishing his round by walking as
far as possible while visiting his last ten houses, which were equally spaced on a straight road.
Assuming a distance of 1 unit between each house, what is the longest distance he could
walk, starting at house 1 and visiting each other house once? What if he started at
house 2? 3? 4? 5?
Source: Based on The
Penguin Book of Curious and Interesting Puzzles, David Wells, #535.
Solutions were received from Alan O'Donnell, Al Zimmermann, Jimmy Chng Gim Hong, Joseph
DeVincentis, Jozef Hanenberg, Bernie Erickson, and Saw L.B. Jozef
Hanenberg's solution is a good summary:
Suppose first that the postman returns to his
starting point at the end of his round. In that case it doesn't matter
where he starts, because his route forms a cycle. To make his route as long as
possible he must alternately visit a house in the first half ( 1 to 5 )
and a house in the second half ( 6 to 10 ) Further it doesn't matter
in which order he picks his numbers.
The table below illustrates the situation: between
two houses is given the number of times that this distance is being
walked.
house nr 1
2 3
4 5
6 7
8 9
10
2x 4x 6x
8x 10x 8x
6x 4x
2x
Total distance in such a cycle is 50 units.
If the postman doesn't return to his starting
point, he can make his route as long as possible by ending his route at house
nr 6, thereby minimizing the number of non-walked units in a cycle-route of
50.
starting point nr 1 45 units
starting point nr 2 46 units
starting point nr 3 47 units
starting point nr 4 48 units
starting point nr 5 49 units.
Mail to Ken