Shortest route to take when delivering Christmas presents?

Question

Huntsville is a small town with only six families. There is at least one child in each family which is on Santa's "nice" list.

The Oskerville's house is five kilometers from the Huntsman's house. The Jones's house is 11 kilometers from the Huntsman's, the Potter's house is 17 kilometers from the Jones's house, the Oskerville's house is 17 kilometers form the Logan's house and 16 kilometers from the Potter's house, the Kruger's house is 14 kilometers from the Oskerville's house, 8 kilometers from the Huntsman's house, 4 kilometers from the Jones's house, 20 kilometers from the Potter's house, and 3 kilometers from the Logan's house.

Find the best route for Santa to take when he delivers presents to the families in Huntsville.

Answer 1

Hey Angus -- here's the "coding" ... HO5 HJ11 JP17 LO17 PO16 KO14 HK8 JK4 KP20 KL3 ...

 

Start with JKL = 7 ... HOP = 21 ... Consider HJ11 HK8 ... Avoid OK14 OL17 PJ17 PK20 ...

 

Try POHJKL = 39 ...  Best regards, sir :) 

Answer 2

I agree with the solution by Andre-W. Here is a systematic way to show 39 is the shortest path for Santa.

Each house except the first and last must be visited and exited. And I claim any path that does not include the minimum paths in and out of at least one node will fail. So, if you select the minimum in and out paths for each node then

1. For Huntsman the minimum paths are 5 and 8
2. For Logan the minimum paths are 3 and 16
3  For Jones the minimum paths are 11 and 4
4. For Oskerville the minimum paths are 5 and 14
5. For Potter the minimum paths are 16 and 17
6. For Kruger the minimum paths are 3 and 4

If we start with any one of these nodes, then three initial nodes in the path are determined.

If you start with Kruger, then the partial path is Logan-Kruger-Jones. To continue, the entrance for Logan should be 16 from Potter because 3 is already used. Likewise for Jones, the exit path is 11 to Huntsville. Now you have Potter-Logan-Kruger-Jones-Huntsville. To add Oskerville, the shortest path is 5 from Huntsville. So that gives Andre's solution.

Starting from Huntsman you get the initial path Oskerville-Huntsman-Kruger for a total of 13; but then you need to use Logan-Oskerville-Huntsman-Kruger-Jones for a total of 34. Now you need to get from Jones to Potter which adds 17.  Too high.

Starting from Jones you get Huntsman-Jones-Kruger, and then Oskerville-Huntsman-Jones-Kruger-Logan for a total of only 23. But now you have to get from Logan to Potter which gives 39, equivalent to the Andre's solution in km.  This is a second solution to the problem.

Starting with Oskerville you get Huntsman-Oskerville-Kruger, and then Jones-Huntsman-Oskerville-Kruger-Logan for a total of 33. And to get to Potter you need to add 16. Too high.

Starting with Logan you get Kruger-Logan-Potter, and then Jones-Kruger-Logan-Potter-? But now you can't go from Potter to anywhere without retracing. So what about Jones? Huntsville-Jones-Kruger-Logan-Potter that's 34. Now you need to add the last location Oskerville, giving Oskerville-Huntsville-Jones-Kruger-Logan-Potter which is a duplicate of a solution above - total 39.

Starting with Potter you get Logan-Potter-Jones for a total of 33 already. This obviously won't yield a minimum.

Unless I've missed something, these are the only candidates for minimum path length for Santa.  

Answer 3

I takes at least 5 trips to get to all 6 families. If we assume no trip is made twice, the minimum distance traveled would be 3+4+5+8+16=36 km, because the other distances we are given (17, 17, and 20 km) are all greater than 16. 16, rather than 11, has to be in this minimum set, because that's how far it is at least to get to the Potter family.

So far I only found a route with 39 km:

Logan-3-Kruger-4-Jones-11-Huntsman-5-Oskarville-16-Potter  (or reverse order).