Enigmatic Code

Programming Enigma Puzzles

Tantalizer 498: Check list

From New Scientist #1049, 28th April 1977 [link]

Keen to do their bit for the nation, Aspex Ltd., the aspirin company, have decided to sponsor a chess tournament. There will be four prizes and 13 players will compete on the usual all-against-all basis, with 1 point for each win and ½ for each draw. The prizes will be divisible. Thus if 3 players tie for 1st place they will share the top 3 prizes; if 3 players tie for 3rd place, they will share the 3rd and 4th prizes; and so on.

As you see, there is no telling in advance how many players will end up with a share in the prizes. But my friend George is determined to be among them. Not for him a cliff-hanging struggle for top place, which might leave him prizeless, if boldness does not pay! What he wants to know is exactly how few points he needs to collect from his 12 games to be absolutely sure of featuring on the prize list.

Can you help him?

[tantalizer498]

Advertisements

One response to “Tantalizer 498: Check list

  1. Jim Randell 9 November 2016 at 8:54 am

    Here is the setters solution:

    Answer: 10 points.

    If he scored only 9½, there could be 4 other players who together scored 6 points from their games against each other and (36 − 1½) in their other games, the 1½ being the minimum they would have to cede to George.

    And here’s my programmatic solution:

    We are interested in finding the minimum score that guarantees winning a prize. So we can look for the maximum score where four of the players can achieve a better score (and therefore win all the prizes). The minimum winning score is a half-point more than this maximum losing score.

    This Python 3 program considers decreasing possible total scores until it finds one where four players can achieve a better score and so take all the prizes. It runs in 207ms.

    from enigma import irange, arg, printf
    
    # to keep things in integers we work with "half-points"
    
    # decompose total score <t> among <n> games that we want the results
    # for and <k> other games that we don't need the results for
    def decompose(t, n, k, s=[]):
      # are we done?
      if n == 0:
        if 0 <= t <= 2 * k:
          yield s
      else:
        # 2 = win, 1 = draw, 0 = lose
        for x in (2, 1, 0):
          if not(x > t):
            yield from decompose(t - x, n - 1, k, s + [x])
    
    # find the numbers of half points that don't guarantee a prize
    # N = number of opponents
    # P = number of prizes
    def solve(N, P):
      # maximum number of points available
      M = 2 * N
      # we only need to work out scores against the P opponents who do better
      # than us, the remaining N - P are the "rest"
      R = N - P
    
      # t = total score to achieve
      # n = number of "better" opponents to find
      # d = delta for better opponents (1 for the first, 0 for remaining)
      # ts = total scores achieved so far
      # ss = score in individual games so far
      def _solve(t, n, d=1, ts=[], ss=[]):
        # are we done?
        if n < 0:
          yield ts
        else:
          # subtract games already played
          p = t - sum((2 - s[n]) for s in ss)
          # determine scores against the prize winners
          for s in decompose(p, n, R):
            # and the next prize winner scores (t + d) or more
            for q in irange(t + d, M):
              yield from _solve(q, n - 1, 0, ts + [t], ss + [s])
    
      # consider possible totals for the highest loser
      for t in irange(M, 0, step=-1):
        yield from _solve(t, P)
    
    # N = number of opponents (one less that the number of players)
    # P = number of shared prizes
    N = arg(12, 0, int)
    P = arg(4, 1, int)
    
    # find the largest number of half-points that don't guarantee a prize
    for ts in solve(N, P):
      m = (ts[0] + 1.0) * 0.5
      printf("[N={N} P={P}] min winning score = {m} {ts}", ts=list(x * 0.5 for x in ts))
      break
    

    Solution: George must score at least 10 points to be sure of getting a prize.

    Here is an example where George (Player E) scores 9½ points, but fails to win a prize as players A, B, C, D have all scored more points than him.

    tantalizer-498-solution

    There are the following options to score 10 points from 12 matches:

    10 wins (2 losses)
    9 wins + 2 draws (1 loss)
    8 wins + 4 draws (0 losses)

    I’m not sure this changes George’s strategy much, he can only afford to lose at most 2 of the 12 matches.

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: