Puzzle Time - The out-of-shape postman
-
PUZZLE: The Out-of-Shape Postman
A postman has deliveries to make on a long street, to addresses 2, 3, 5, 7, 11, 13, 17, and 19. The distance between any two houses is proportional to the difference of their addresses.
To minimize the distance travelled, the postman would of course make his deliveries in increasing (or decreasing) order of address. But our postman is out of shape and would like to maximize the distance travelled making these deliveries, so as to get the most exercise he can. But he can't just wander around town; to do his job properly he is obligated to walk directly from each delivery to the next one.
In what order should he make his deliveries?
-
In any order? Ay particular starting and stopping point?
Here's another hint.
||Calculate the maximum number of times you could traverse each path segment. Can you find a path that achieves the maximum?||
-
In any order? Ay particular starting and stopping point?
Here's another hint.
||Calculate the maximum number of times you could traverse each path segment. Can you find a path that achieves the maximum?||
-
@jon-nyc said in Puzzle Time - The out-of-shape postman:
In any order? Ay particular starting and stopping point?
The next point is always the one that is the farthest from the current. That's the obvious "greedy" algorithm.
-
Here's the answer, I'm not bothering with a spoiler.
A previous hint suggested figuring out the maximum number of times you could traverse any segment of road between two addresses.
Let me label the path segments between the addresses with letters as follow:
2-a-3-b-5-c-7-d-11-e-13-f-17-g-19
It's clear that you could traverse a and g a maximum of twice. Once arriving to the end point and once leaving it. In order to traverse them the maximum number of times you can't start or end on either end point, if that condition is met it guarantees you'll traverse a and g the maximum number of times.
b (and f) you can traverse a maximum of 4 times. In the case of b, you could traverse it once going to 3, once leaving 3, once going to 2, and once leaving 2. (of course you could do it less but that's the max). What condition must be met to traverse b the maximum number of times? You can't start or finish on either the end point 2 or the next point 3. You also can't go from 2 to 3 or vice versa. Same with f since they are mirror images of each other.
Similarly c and e can be traversed 6 times. Also the constraints are similar. You can't start or end on either 2,3,5 (or 19,17,13). And you can't travel directly between the three end points. IOW, each trip to or from the three end points needs to cross segment c (e).
Segment d can be traversed as much as 7 times. What condition must be met in order to traverse it the maximum number of times? Well, there are only 8 addresses, so 7 'trips' between them. Each trip must cross segment d.
If you take all of that together, it means we must start at one of the two middle points (7 or 11), we must end at the other one, and we must cross the middle segment each time we move from one address to another. So we zig zag back and forth.
You can do what Klaus suggested and always go to the furthest on the other side. But a little reflection will show you it doesn't actually matter the order you take them in, as long as you cross the middle each time and start and end in the right spot.
A little math will show there are actually 2x3x3x2x2 = 72 ways to hit that maximum distance, which is 82.
Note also that the distances between the houses don't matter at all.
-
Here's the answer, I'm not bothering with a spoiler.
A previous hint suggested figuring out the maximum number of times you could traverse any segment of road between two addresses.
Let me label the path segments between the addresses with letters as follow:
2-a-3-b-5-c-7-d-11-e-13-f-17-g-19
It's clear that you could traverse a and g a maximum of twice. Once arriving to the end point and once leaving it. In order to traverse them the maximum number of times you can't start or end on either end point, if that condition is met it guarantees you'll traverse a and g the maximum number of times.
b (and f) you can traverse a maximum of 4 times. In the case of b, you could traverse it once going to 3, once leaving 3, once going to 2, and once leaving 2. (of course you could do it less but that's the max). What condition must be met to traverse b the maximum number of times? You can't start or finish on either the end point 2 or the next point 3. You also can't go from 2 to 3 or vice versa. Same with f since they are mirror images of each other.
Similarly c and e can be traversed 6 times. Also the constraints are similar. You can't start or end on either 2,3,5 (or 19,17,13). And you can't travel directly between the three end points. IOW, each trip to or from the three end points needs to cross segment c (e).
Segment d can be traversed as much as 7 times. What condition must be met in order to traverse it the maximum number of times? Well, there are only 8 addresses, so 7 'trips' between them. Each trip must cross segment d.
If you take all of that together, it means we must start at one of the two middle points (7 or 11), we must end at the other one, and we must cross the middle segment each time we move from one address to another. So we zig zag back and forth.
You can do what Klaus suggested and always go to the furthest on the other side. But a little reflection will show you it doesn't actually matter the order you take them in, as long as you cross the middle each time and start and end in the right spot.
A little math will show there are actually 2x3x3x2x2 = 72 ways to hit that maximum distance, which is 82.
Note also that the distances between the houses don't matter at all.
@jon-nyc said in Puzzle Time - The out-of-shape postman:
Note also that the distances between the houses don't matter at all.
The ‘official’ solution came out today. When discussing a generalized version of the problem, it pointed out that for odd numbers of houses the distance between them matters, but only a little.
In the case an odd number of houses you start and end at the center house and the one closest to it. Otherwise the solution is identical and scales to any number of houses.
