Enigmatic Code

Programming Enigma Puzzles

Enigma 289: All for one

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.

Enigma 289

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

One response to “Enigma 289: All for one

  1. Jim Randell 22 June 2015 at 9:09 am

    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.

    include "globals.mzn";
    
    % there are 20 pupils
    set of int: Pupils = 1..20;
    
    % scores in each paper
    array[Pupils] of var 0..100: Paper1;
    array[Pupils] of var 0..100: Paper2;
    array[Pupils] of var 0..100: Paper3;
    array[Pupils] of var 0..300: Total;
    
    % the total is the sum of the papers
    constraint forall (i in Pupils) (Total[i] == Paper1[i] + Paper2[i] + Paper3[i]);
    
    % there are no ties for any paper, or overall
    constraint alldifferent(Paper1);
    constraint alldifferent(Paper2);
    constraint alldifferent(Paper3);
    constraint alldifferent(Total);
    
    % and the totals are in order
    constraint decreasing(Total);
    
    % Athos was bottom of the class (pupil 20) and got 50 in each paper
    constraint Paper1[20] == 50;
    constraint Paper2[20] == 50;
    constraint Paper3[20] == 50;
    
    % Athos came 13th in Paper 1, 8th in Paper 2, 1st in Paper 3
    constraint sum (i in Pupils) (Paper1[i] > Paper1[20]) == 12;
    constraint sum (i in Pupils) (Paper2[i] > Paper2[20]) == 7;
    constraint sum (i in Pupils) (Paper3[i] > Paper3[20]) == 0;
    
    % Porthos came top of the class (pupil 1)
    % Porthos came 6th in Paper 1, 15th in Paper 2, 20th in Paper 3
    constraint sum (i in Pupils) (Paper1[i] > Paper1[1]) == 5;
    constraint sum (i in Pupils) (Paper2[i] > Paper2[1]) == 14;
    constraint sum (i in Pupils) (Paper3[i] > Paper3[1]) == 19;
    
    % Aramis came 12th overall (pupil 12), and 12th in each paper
    constraint sum (i in Pupils) (Paper1[i] > Paper1[12]) == 11;
    constraint sum (i in Pupils) (Paper2[i] > Paper2[12]) == 11;
    constraint sum (i in Pupils) (Paper3[i] > Paper3[12]) == 11;
    
    % d'Artagnan, was just above Athos (pupil 19)
    % d'Artagnan's score in Paper 2 was +/-2 from Porthos
    
    % the following values are determined analytically
    constraint forall (i in Pupils) (Total[i] == 170 - i);
    constraint Paper1[1] == 95;
    constraint Paper2[1] == 43;
    constraint Paper3[1] == 31;
    constraint Paper1[12] == 73;
    constraint Paper2[12] == 46;
    constraint Paper3[12] == 39;
    % d'Artagnan scored 41 or 45 in Paper 2
    constraint Paper2[19] == 41;
    
    % solve it
    solve satisfy;
    
    % output the solution
    output [
      "Paper 1: " ++ show(Paper1) ++ "\n" ++
      "Paper 2: " ++ show(Paper2) ++ "\n" ++
      "Paper 3: " ++ show(Paper3) ++ "\n" ++
      "Total: " ++ show(Total)
    ];
    

    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).

    Enigma 289 - Solution

    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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: