Edited by Richard Walker, Tuesday, 28 Jul 2020, 21:13
A few days ago I described a problem my friend thought of. Suppose we have a street with 10 houses, each one the same distance from the adjacent houses.
A postman starts at No. 1 and in order to get plenty of exercise decides to visit each house exactly once and return to No. 1 at the end, in such a way that he walks the greatest possible distance. How can he do that, and what is the maxiumum distance?
There are 362800 possible routes he can take, and of those 2880 achieve the greatest possible distance, which is 50. If we divide the houses numbers into two groups, 1-5 and 6-10, then the longest path is any one that travels alternately back and forth between the first group and the second group, visiting each house just once and then returning to No. 1. For example
1, 6, 2, 7, 3, 8, 4, 9, 5, 10, 1
Rather surprisingly the distance is the same whatever order we visit the houses in each group.
The same scheme will give the longest path for any even number of houses. A similar scheme works for an odd number, although in this case we can't completely alternate between right and left; at some point the postman will have to go in the same direction twice running.
A version of this problem was published by Martin Gardner in Scientific American June 1965 and appeared before that in One hundred problems in elementary mathematics by Hugo Steinhaus.
Travelling Mailman Problem Again
A few days ago I described a problem my friend thought of. Suppose we have a street with 10 houses, each one the same distance from the adjacent houses.
A postman starts at No. 1 and in order to get plenty of exercise decides to visit each house exactly once and return to No. 1 at the end, in such a way that he walks the greatest possible distance. How can he do that, and what is the maxiumum distance?
There are 362800 possible routes he can take, and of those 2880 achieve the greatest possible distance, which is 50. If we divide the houses numbers into two groups, 1-5 and 6-10, then the longest path is any one that travels alternately back and forth between the first group and the second group, visiting each house just once and then returning to No. 1. For example
1, 6, 2, 7, 3, 8, 4, 9, 5, 10, 1
Rather surprisingly the distance is the same whatever order we visit the houses in each group.
The same scheme will give the longest path for any even number of houses. A similar scheme works for an odd number, although in this case we can't completely alternate between right and left; at some point the postman will have to go in the same direction twice running.
A version of this problem was published by Martin Gardner in Scientific American June 1965 and appeared before that in One hundred problems in elementary mathematics by Hugo Steinhaus.