Enigmatic Code

Programming Enigma Puzzles

Tantalizer 478: Surprises

From New Scientist #1029, 2nd December 1976 [link]

King Ethelweed needed a new champion. So he commanded his three doughtiest knights to appear before him on the first Monday of the new year and bade them fight one another. They fought all day long until the eventide, when the king called a respite and awarded x ducats to the winner, y ducats to the second knight and z to the third. xy and z are positive descending whole numbers.

To the valiant knights’ dismay, the same happened on the next and each following day, until King Ethelweed at length declared himself satisfied. One each day the same prizes of xy and z were awarded, the being no ties on any day.

Thus it befell that Sir Kay gained the most ducats and became the king’s champion, even though he fared worse on the second day than on the first. Sir Lionel took home twenty ducats in all and Sir Morgan, despite winning top prize on the third day, amassed a mere nine.

Which was the final day and who won how many ducats on it?

[tantalizer478]

Advertisements

2 responses to “Tantalizer 478: Surprises

  1. Jim Randell 28 June 2017 at 7:46 am

    As x, y, z are decreasing positive integers the smallest possible values they can take on is: x=3, y=2, z=1.

    And M wins the top prize on the third day, but ends up with 9 points, so the maximum value of x is 9 – 1 – 1 = 7.

    So there is a relatively small number of (x, y, z) values to consider.

    This Python 3 program runs in 64ms.

    from itertools import permutations
    from enigma import irange, printf
    
    # given (x, y, z) values find possible outcomes
    # K, L, M = totals so far
    # s = sequence of prizes for each day (K, L, M)
    def solve(x, y, z, K=0, L=0, M=0, s=[]):
      n = len(s)
      # is this a possible outcome?
      if n > 2 and K > 20 and L == 20 and M == 9:
        yield (n, K, L, M, s)
      else:
        # award the prizes
        for (k, l, m) in permutations((x, y, z)):
          # K did worse on the second day than the first
          if n == 1 and not(k < K): continue
          # M won top prize on day 3
          if n == 2 and not(m == x): continue
          # find the new totals
          (K2, L2, M2) = (K + k, L + l, M + m)
          if not(L2 > 20 or M2 > 9):
            yield from solve(x, y, z, K2, L2, M2, s + [(k, l, m)])
    
    # consider possible values for x, y, z
    for x in irange(3, 7):
      for y in irange(2, x - 1):
        for z in irange(1, y - 1):
          # find possible solutions
          for (n, K, L, M, s) in solve(x, y, z):
            printf("{n} days, x={x} y={y} z={z}, K={K} L={L} M={M}, {s}")
    

    Solution: On the 5th and final day, Lionel won 5 ducats, Kay won 4 ducats, Morgan won 1 ducat.

    The full results are:

    Day 1: 1st = K (5), 2nd = L (4), 3rd = M (1)
    Day 2: 1st = L (5), 2nd = K (4), 3rd = M (1)
    Day 3: 1st = M (5), 2nd = K (4), 3rd = L (1)
    Day 4: 1st = L (5), 2nd = K (4), 3rd = M (1)
    Day 5: 1st = L (5), 2nd = K (4), 3rd = M (1)
    Total: 1st = K (21), 2nd = L (20), 3rd = M (9)

    K only got one 1st place, but the 4 second places (and no last places) gave him the tournament. L got 3 first places, but also one last place (on day 3) which lost him the tournament. M is the clear loser, coming last on 4 of the 5 days.

  2. Brian Gladman 29 June 2017 at 10:01 am
    from itertools import combinations, count, permutations
    
    # run a round in the contest with the three prizes in the
    # tuple <vals>, the day in <day> and a tuple of tuples in
    # <res> (in the order winner..loser) that give the scores 
    # for the contestants on each of the days
    def run_round(vals, day=0, res=[]):
    
      if day > 2:
        # find the accumulated ducats for each contestant
        pts = [sum(r) for r in zip(*res)]
        # either or both the second and third contestants 
        # have exceeded their final amounts
        if pts[1] > 20 or pts[2] > 9:
          return
        # the winner has more than 20 ducats, the second
        # and third have 20 and 9 ducats respectively
        if pts[0] > 20 and pts[1] == 20 and pts[2] == 9:
          yield day, res
      
      # try all distributions of the prizes on this day
      for p in permutations(vals):
        # the winner must do worse on the second day
        if day != 1 or p[0] < res[0][0]:  
          # the loser wins on the third day
          if day != 2 or p[2] == vals[2]:
            # continue on to the next day
            yield from run_round(vals, day + 1, res + [p])
    
    # consider the maximum award given on on each round
    for c in count(3):
      # choose three vales for the awards
      for vals in combinations(range(1, c + 1), 3):
        # and find any solutions for this set of awards
        for d, r in run_round(vals):
          print('Ducats (days 1..{}) K:{}, L:{} and M:{}.'.format(d, *zip(*r)))
          exit()
    

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: