Sunday Times Teaser 2744 – School Run

by Angela Newing

Published: 26 April 2015 (link)

Each of the three houses of Merryhouse School entered four students in the cross-country race. Points were awarded with 12 for the winner, 11 for second, and so on down to 1 for the tail-ender (from Berry House). When the points were added up, all houses had equal points. Three of the runners from Cherry House were in consecutive positions, as were just the two middle-performers from Derry House.

Which house did the winner come from, and what were the individual scores of its runners?

One Comment Leave one →

Brian Gladman permalink


# The points for each house are (1 + 2 + ... + 12) / 3 = 26

# consider the middle of the three consecutive scores for
# Cherry (the range set by constraints on the fourth score)
for c in range(5, 9):
  c4 = 26 - 3 * c
  c_pts = set((c - 1, c, c + 1, c4))
  # ensure four different scores, only three consecutive
  if len(c_pts) == 4 and (c4 < c - 2 or c4 > c + 2):
    
    # now consider the points for the middle two Derry runners
    for d in range(4, 11):
      # which must be disjoint from those for Cherry
      if not (d in c_pts or d + 1 in c_pts):
        # one Derry runner has fewer points than this pair,
        # the other higher, neither consecutive
        for d1 in range(2, d - 1):
          d4 = 25 - 2 * d - d1
          # ensure non-consecutive and no overlap with Cherry
          if d + 2 < d4 < 13 and not (d1 in c_pts or d4 in c_pts):
            d_pts = set((d1, d, d + 1, d4))
            
            # the remaining points are now those for Berry
            b_pts = set(range(1, 13)) - (c_pts | d_pts)
            
            # find the house with the winner
            s = sorted(((n, tuple(sorted(p, reverse=True))) for n, p in
                  (('Berry', b_pts), ('Cherry', c_pts), ('Derry', d_pts))), 
                       reverse=True, key=lambda x: 12 in x[1])

            print('{0[0]:} with points {0[1]:} [{1:}, {2:}]'.
                      format(s[0], s[1], s[2]))

# The points for each house are (1 + 2 + ... + 12) / 3 = 26

# consider the middle of the three consecutive scores for

# Cherry (the range set by constraints on the fourth score)

for c in range(5, 9):

c4 = 26 - 3 * c

c_pts = set((c - 1, c, c + 1, c4))

# ensure four different scores, only three consecutive

if len(c_pts) == 4 and (c4 < c - 2 or c4 > c + 2):

# now consider the points for the middle two Derry runners

for d in range(4, 11):

# which must be disjoint from those for Cherry

if not (d in c_pts or d + 1 in c_pts):

# one Derry runner has fewer points than this pair,

# the other higher, neither consecutive

for d1 in range(2, d - 1):

d4 = 25 - 2 * d - d1

# ensure non-consecutive and no overlap with Cherry

if d + 2 < d4 < 13 and not (d1 in c_pts or d4 in c_pts):

d_pts = set((d1, d, d + 1, d4))

# the remaining points are now those for Berry

b_pts = set(range(1, 13)) - (c_pts | d_pts)

# find the house with the winner

s = sorted(((n, tuple(sorted(p, reverse=True))) for n, p in

(('Berry', b_pts), ('Cherry', c_pts), ('Derry', d_pts))),

reverse=True, key=lambda x: 12 in x[1])

print('{0[0]:} with points {0[1]:} [{1:}, {2:}]'.

format(s[0], s[1], s[2]))

and here is a solution in MiniZinc a constraint programming language:


include "globals.mzn";

% the number of houses
int : houses = 3;

% the house names
array [1..houses] of string : name = ["Berry", "Cherry", "Derry"];

% the number of runners in each house
int : runners = 4;

% the score for each house
int : house_score = sum(1 .. houses * runners) div 3;

% the possible scores
set of int : points = 1 .. houses * runners;

% the scores for the runners in Berry, Cherry and Derry
array[1 .. runners] of var points : b;
array[1 .. runners] of var points : c;
array[1 .. runners] of var points : d;

% all scores are different
constraint alldifferent(b ++ c ++ d);

% the house scores are all equal
constraint sum(b) == house_score / sum(c) == house_score 
                                 / sum(d) == house_score;

% the last person to finish is in Berry
constraint b[1] > b[2] / b[2] > b[3] / b[3] > b[4] / b[4] == 1;

% three scores in Cherry are consecutive
constraint c[1] == c[2] + 1 / c[2] == c[3] + 1 / c[4] < c[3] - 1 /
           c[1]  > c[2] + 1 / c[2] == c[3] + 1 / c[3] == c[4] + 1;

% the middle two scores in Derry are consecutive
constraint d[1] > d[2] + 1 / d[2] == d[3] + 1 / d[3] > d[4] + 1;

solve satisfy;

output [ show(name[1]) ++ " = " ++ show(b) ++ ", " ++ 
         show(name[2]) ++ " = " ++ show(c) ++ ", " ++
         show(name[3]) ++ " = " ++ show(d) ++ ", " ];

include "globals.mzn";

% the number of houses

int : houses = 3;

% the house names

array [1..houses] of string : name = ["Berry", "Cherry", "Derry"];

% the number of runners in each house

int : runners = 4;

% the score for each house

int : house_score = sum(1 .. houses * runners) div 3;

% the possible scores

set of int : points = 1 .. houses * runners;

% the scores for the runners in Berry, Cherry and Derry

array[1 .. runners] of var points : b;

array[1 .. runners] of var points : c;

array[1 .. runners] of var points : d;

% all scores are different

constraint alldifferent(b ++ c ++ d);

% the house scores are all equal

constraint sum(b) == house_score / sum(c) == house_score

/ sum(d) == house_score;

% the last person to finish is in Berry

constraint b[1] > b[2] / b[2] > b[3] / b[3] > b[4] / b[4] == 1;

% three scores in Cherry are consecutive

constraint c[1] == c[2] + 1 / c[2] == c[3] + 1 / c[4] < c[3] - 1 /

c[1] > c[2] + 1 / c[2] == c[3] + 1 / c[3] == c[4] + 1;

% the middle two scores in Derry are consecutive

constraint d[1] > d[2] + 1 / d[2] == d[3] + 1 / d[3] > d[4] + 1;

solve satisfy;

output [ show(name[1]) ++ " = " ++ show(b) ++ ", " ++

show(name[2]) ++ " = " ++ show(c) ++ ", " ++

show(name[3]) ++ " = " ++ show(d) ++ ", " ];

Sunday Times Teaser 2744 – School Run

by Angela Newing

Published: 26 April 2015 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta