Enigma 1435 – A good sign
Like many people I read the New Scientist on a weekly basis. One of the things that annoys me is the weekly (usually) maths based puzzle Enigma.
This week’s puzzle is thus:
The distance between any pair of the villages Aville, Bestown, Chipping and Dreem is a whole number of miles. A signpost in each village gives the distances to the other villages, but each sign has a different number of correct distances. The signs are as follows:
From Aville
- Bestown 7
- Chipping 9
- Dreem 9
From Bestown
- Aville 8
- Chipping 7
- Dreem 9
From Chipping
- Aville 8
- Bestown 9
- Dreem 7
From Dreem
- Aville 7
- Bestown 8
- Chipping 9
I recently did a round walk, of less than 30 miles, visiting each village and ending back where I started.
List (in the order AB, AC, AD, BC, BD, CD) the distances between the villages.
This appears to be a straight forward Traveling Sales Person problem, where the person walking around travels along a simple Hamiltonian cycle. (There are a number of assumptions about the problem here – the wording of “I did a round walk,…, visiting each village..” is quite ambiguous, so a number of assumptions are necessary)
Starting with the 6 bidirectional pairs (ie. A>B == B>A), we can see that when written out no two values from the sign posts are the same. From the question we can deduce that while its impossible for both to be correct, both CAN be incorrect.
From the fact that the 4 signs can have 0,1,2, or 3 errors we can see that there are a total of 6 errors across the signs. 6 of the 12 distances are incorrect.
As the hamiltonian cycle must be LESS THAN (not less than or equal to) the only two ways to do this with the possible values from the 6 remaining values are with either a cycle of 7, 7, 7, 7, or 7, 7, 7, 8. Any more and the total becomes 30.
By elimination, we get the following values:
- A-B = 8
- B-C = 7
- C-D = 7
- D-A = 7
Once we’ve got these values all we need to do is figure out the remaining diagonal values that will satisfy the 0,1,2,3 errors condition. After testing we get the values of A-C=8 and B-D=9 that work with all the conditions.
From this, we have Aville with 3 errors, Bestown 0 errors, Chipping 1 error and Dreem 2 errors.
To get the final requested solution in the order AB, AC, AD, BC, BD, CD, we get the end solution –
8, 8, 7, 7, 9, 7
Or if you wish, here’s a diagramatic layout of the towns.
Oh what fun. Will this become a regular feature? Who knows? Not me. All depends if I can do next weeks really. Until then.