Enigmatic Code

Programming Enigma Puzzles

Tantalizer 438: Spring collection

From New Scientist #989, 26th February 1976 [link]

The task of collecting funds for the Red Cross in our little town falls on five married couples. Each spring they make a sort of race of it. The last occasion was very exciting. The couples all started on a different day but, having started, kept at it until the last Friday in March. Each collected the same amount each day but the amount in question was different for each couple.

A different couple was in the lead at nightfall on the final Monday, Tuesday, Wednesday, Thursday and Friday. In other words, each couple led once in the final week. At the close on Friday, Pamela and Albert held the position held by Edward and his wife on Monday night. At the close on Friday Queenie and Bill held the position held by Desmond and wife on Monday night. Similarly Rose and husband finished where Charlie and wife had been on Monday night and Sue and husband finished where Bill and Queenie had been on Monday night. Sue and husband were in the lead on Tuesday night. Queenie and Bill overtook Tania and husband during the final week. All couples had collected something by Monday nightfall.

What was the order at close of play?


One response to “Tantalizer 438: Spring collection

  1. Jim Randell 9 January 2019 at 7:45 am

    All couples are accumulating their totals at a steady rate, so if we were to draw a graph plotting the couples total against time, each couple would be represented by a straight line with a positive slope. And each line would intercept the time axis on a day boundary (a negative integer, if we have t=0 to be the total collected by the end of Monday, t=1 the total collected by the end of Tuesday, etc).

    So, when couple X overtake couple Y, they are behind at all times before the intersection, and ahead at all times after the intersection. i.e. couple X’s line has a steeper slope than couple Y.

    The couple in the lead on Monday (couple 1), is overtaken by couple 2 by Tuesday, so by Friday couple 2 will still be ahead of couple 1. Couple 2 is overtaken by couple 3 on Wednesday, so by Friday couple 3 will still be ahead of couple 2 (who will be ahead of couple 1). Couple 3 is overtaken by couple 4 on Thursday, so by Friday couple 4 is still ahead of couple 3 (who are ahead of couple 2, who are ahead of couple 1). And finally, on Friday, couple 4 is overtaken by couple 5, which gives the final order on Friday as:

    1st = Couple 5; 2nd = Couple 4; 3rd = Couple 3; 4th = Couple 2; 5th = Couple 1

    And this is also the order of the slopes starting with the steepest.

    A similar argument working with the days is reverse order, tells us the order of the couples on Monday is the reverse of this.

    The equation of the line will be:

    y(t) = a(t + d)

    where a is the daily amount collected and d is the number of days the couple have been collecting on Monday.

    If we suppose the couples start collecting Thursday, Friday, Saturday Sunday, Monday; then couple 1 collects at the slowest rate, say m1 units of currency per day, and starts the earliest. The equations for each couple are:

    y1(t) = m1(t + 5)
    y2(t) = m2(t + 4)
    y3(t) = m3(t + 3)
    y4(t) = m4(t + 2)
    y5(t) = m5(t + 1)

    At t=0 couple 1 is in the lead, but at t=1 couple 2 is in the lead:

    y1(0) > y2(0), y2(1) > y1(1)

    5 m1 > 4 m2, 5 m2 > 6 m1

    (6/5) m1 < m2 < (5/4) m1

    Similarly, by considering t = 1, 2, 3, 4, we get:

    (6/5) m2 < m3 < (5/4) m2
    (6/5) m3 < m4 < (5/4) m3
    (6/5) m4 < m5 < (5/4) m4

    If we start setting: m1 = 1.00, and choosing a value in the middle of the range at each stage, we get:

    m1 = 1.00
    m2 = 1.22
    m3 = 1.49
    m4 = 1.82
    m5 = 2.22

    So if we start on the Thursday of the previous week, with a couple starting on each consecutive day, the totals at the end of the day are:

    Thu: C1 = 1.00
    Fri: C1 = 2.00, C2 = 1.22
    Sat: C1 = 3.00, C2 = 2.43, C3 = 1.49
    Sun: C1 = 4.00, C2 = 3.66, C3 = 2.98, C4 = 1.82
    Mon: C1 = 5.00, C2 = 4.88, C3 = 4.47, C4 = 3.64, C5 = 2.22 (order = C1, C2, C3, C4, C5)
    Tue: C1 = 6.00, C2 = 6.10, C3 = 5.96, C4 = 5.46, C5 = 4.44(order = C2, C1, C3, C4, C5)
    Wed: C1 = 7.00, C2 = 7.32, C3 = 7.45, C4 = 7.28, C5 = 6.66 (order = C3, C2, C4, C1, C5)
    Thu: C1 = 8.00, C2 = 8.54, C3 = 8.94, C4 = 9.10; C5 = 8.88 (order = C4, C3, C5, C2, C1)
    Fri: C1 = 9.00, C2 = 9.76, C3 = 10.43, C4 = 10.92, C5 = 11.10 (order = C5, C4, C3, C2, C1)

    And we see this satisfies the conditions.

    Here is the graph:

    On the Monday (x=0) we see couple 1 (red) is slightly ahead of couple 2 (orange), and then we have couples 3, 4, 5 (green, blue, purple).

    On the Tuesday (x=1) we see couple 2 (orange) has overtaken couple 1 (red), and then we have couples 3, 4, 5 (green, blue, purple).

    On the Wednesday (x=2) we see couple 3 (green) is slightly ahead of couple 2 (orange) and couples 4, 1, 5 (blue, red, purple).

    On the Thursday (x=3) we see couple 4 (blue) is ahead of couples 3 and 5 (green, purple), then couples 2, 1 (orange, red).

    On the Friday (x=4) we see couple 5 (purple) is in the lead, followed by couple 4 (blue), couple 3 (green), couple 2 (orange) and couple 1 (red).

    The final order is the reverse of the original order, and the relative positions will remain as the lines diverge.

    So does this make a viable solution?

    By assigning the following couples we satisfy all the conditions of the puzzle:

    Couple 1 = E & T
    Couple 2 = D & S
    Couple 3 = C & R
    Couple 4 = B & Q
    Couple 5 = A & P

    And this is the only possible assignment, so this gives us the required answer:

    Solution: On Friday night the order was: 1st = Albert & Pamela; 2nd = Bill & Queenie; 3rd = Charlie & Rose; 4th = Desmond & Sue; 5th = Edward & Tania.

    But are there other solutions? Certainly we can choose different amounts for m1, …, m5, and different starting days for the couples. This will give us a slightly different graph, with different crossing points, but the order on Friday is always the same (and is always the reverse of the order on Monday).

    This MiniZinc model of the problem generates possible pairings and a table of positions for each couple on each day that satisfies the constraints given in the puzzle, but doesn’t determine actual amounts for each couple, so it does not verify that it is always possible to construct a graph for each scenario.

    However, it does find 64 different tables, but each has the same pairings and (as expected) the same ordering of couples on Monday and Friday, so this must also be the case for all possible graphs. Hence the solution to the puzzle is unique, and we have demonstrated a possible set of values that verifies it.

    Here is the MiniZinc model:

    %#! mzn-gecode -a
    include "globals.mzn";
    % couples are assigned a number from 1 to 5
    % male partners
    var 1..5: A;
    var 1..5: B;
    var 1..5: C;
    var 1..5: D;
    var 1..5: E;
    constraint all_different([A, B, C, D, E]);
    % female partners
    var 1..5: P;
    var 1..5: Q;
    var 1..5: R;
    var 1..5: S;
    var 1..5: T;
    constraint all_different([P, Q, R, S, T]);
    % label the days
    int: Mon = 1;
    int: Tue = 2;
    int: Wed = 3;
    int: Thu = 4;
    int: Fri = 5;
    % x[<day>, <couple>] = <position>
    array [1..5, 1..5] of var 1..5: x;
    % each couple is placed on each day
    constraint forall (d in 1..5) (all_different([x[d, i] | i in 1..5]));
    % couple i is 1st on day i
    constraint forall (i in 1..5) (x[i, i] = 1);
    % a couple cannot overtake another couple more than once
    constraint forall (i, j in 1..5 where i < j) (sum (d in 1..4) ((x[d, i] < x[d, j]) != (x[d + 1, i] < x[d + 1, j])) < 2);
    % additional constraints from the puzzle text:
    % A & P are a couple
    constraint A = P;
    % B & Q are a couple
    constraint B = Q;
    % A's position on Friday is the same as E's position on Monday
    constraint x[Fri, A] = x[Mon, E];
    % B's position on Friday is the same as D's position on Monday
    constraint x[Fri, B] = x[Mon, D];
    % R's position on Friday is the same as C's position on Monday
    constraint x[Fri, R] = x[Mon, C];
    % S's position on Friday is the same as B's position on Monday
    constraint x[Fri, S] = x[Mon, B];
    % S's position on Tuesday is 1st
    constraint x[Tue, S] = 1;
    % B overtook T during the week
    constraint (x[Mon, T] < x[Mon, B]) /\ (x[Fri, B] < x[Fri, T]);
    solve satisfy;

    And here is a Python program that uses the minizinc.py wrapper to produce more readable output, and confirm the pairings and Friday orders are always the same:

    from collections import Counter
    from enigma import irange, unpack, join, sprintf, printf
    from minizinc import MiniZinc
    # count results
    r = Counter()
    # the MiniZinc formulation of the puzzle
    p = MiniZinc("tantalizer438.mzn")
    for (A, B, C, D, E, P, Q, R, S, T, x) in p.solve(result="A B C D E P Q R S T x"):
      # map couple number to male and female partners
      m = dict(zip((A, B, C, D, E), "ABCDE"))
      f = dict(zip((P, Q, R, S, T), "PQRST"))
      # print the order on each day
      for (d, s) in enumerate(("Mon", "Tue", "Wed", "Thu", "Fri"), start=1):
        order = dict((p, i) for (i, p) in x[d].items())
        t = join((sprintf("{k} = {m}+{f}", m=m[order[k]], f=f[order[k]]) for k in sorted(order.keys())), sep="; ")
        printf("{s}: {t}")
        # record Friday's order
        if d == 5: r[t] += 1
    # output solutions
    for (k, v) in r.most_common():
      printf("{k} [{v} solutions]")

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: