Enigmatic Code
Programming Enigma Puzzles
Enigma 289: All for one
Posted by on 22 June 2015
From New Scientist #1437, 3rd January 1985 [link]
If the records in the 1926 mark book of class IVB of Henrietta High School are to be believed — and there are those who doubt their authenticity — then that year saw a set of examination results which must be unique for their sheer perversity. The performance of three of the 20 pupils (bearing the suspiciously coincidental names of Athos, Porthos and Aramis) are shown below.
As you can see, the end-of-the-year exams consisted of three papers. The overall form positions were determined merely by adding the marks achieved in the three papers. On the face of it, Athos appears to have done better than average. Yet you will begin to see what is so odd about the results when I tell you that Athos actually came bottom of the class overall. Porthos, with results which would normally merit the comment “room for improvement”, was in fact top. Meanwhile, Aramis’s steady performance was reflected in his coming 12th overall. To add to the intrigue, I can tell you that Athos got 50 out of 100 in all three papers.
Information about the fourth member of the class “d’Artagnan”, is scant. However, I can tell you that his mark in Paper 2 was 2 higher (or was it 2 lower?) than Porthos’s, and that he came next to bottom in the class. Given that there were no ties at any stage from places in any list, how many marks did d’Artagnan get in Paper 1?
[enigma289]
Advertisements
First a bit of analysis:
If Athos scores 50 in each paper his total score is 150, and he is bottom of the class.
Porthos is top of the class, so his total score has to be at least 169 (so we can fit 18 distinct total scores between Athos and Porthos).
In Paper 1, Athos came 13th with 50 points, and Porthos came 6th, so his score must be between 57 and 95 points.
In Paper 2, Athos came 8th with 50 points, and Porthos came 15th, so his score must be between 5 and 43 points.
In Paper 3, Athos came 1st with 50 points, and Porthos came 20th, so his score must be between 0 and 31 points.
By summing these scores that maximum total score Porthos can possibly have is 95 + 43 + 31 = 169, but this is also his minimum possible total score, so: Porthos scored 95 in Paper 1, 43 in Paper 2, 31 in Paper 3, to give a total of 169.
But 169 is the lowest possible score to allow 18 distinct total scores between Athos and Porthos, so the totals are consecutive from Porthos (1st with 169) down to Athos (20th with 150). Which means Aramis is 12th overall with a total of 158 and d’Artagnan is 19th overall with a total of 151.
In Paper 3 Athos was 1st with 50 points and Porthos was 20th with 31 points, so the marks are all the consecutive numbers between 31 and 50. So Aramis’s 12th place score in Paper 3 is 39.
In Paper 2 Athos was 8th with 50 points and Porthos was 15th with 43 points, so all intermediate positions must be consecutively numbered. Hence Aramis was in 12th place with 46 points.
Overall Aramis scored 158 points, so he must have scored 158 – (39 + 46) = 73 points in Paper 1.
But in Paper 1 Aramis is in 12th place with 73 points and Athos is in 13th place with 50 points, so of the remaining pupils 11 scored more than 73 points and 7 scored less than 50 points. Porthos was 6th with 95 points, so the first 5 places must be 100, 99, 98, 97, 96, leaving 5 pupils (7th to 11th places) who must have scores between 94 and 74.
Now if we consider d’Artagnan, we are told he scored either 2 more (or 2 less) than Porthos in Paper 2. If we didn’t have the bracketed text we would know d’Artagnan scored 45 points in Paper 2, and between 32 and 49 (but not 39) points in Paper 3. Since his total score is 151 we can determine possible scores for Paper 1 given a value for Paper 3, and eliminate possibilities that give a scores for Paper 1 between 50 and 73. That leaves only one possibility:
Paper 1 = 74; Paper 2 = 45; Paper 3 = 32.
But with the text in brackets there is also the possibility that d’Artagnan scored 2 points less than Porthos in Paper 2, i.e. he scored 41 points.
I wrote as set of constraints in MiniZinc to attack this possibility, and it determines that the constraints are not satisfiable in 383ms.
So, if there is a solution to the problem the scores for d’Artagnan must be those given above.
Solution: d’Artagnan scored 74 in Paper 1.
If we change line 57 to look for solutions where d’Artagnan scores 2 more than Porthos in Paper 2 (i.e. d’Artagnan scores 45), then Minizinc finds an example solution in 153ms (using mzn-g12lazy).
If we pass the -a argument to mzn-g12lazy, we see that there are many possible solutions. I got to over 2.4 million before the MiniZinc process consumed all the memory on my machine and slowed to a crawl.