Enigmatic Code

Programming Enigma Puzzles

Enigma 1073: Cross-country match

From New Scientist #2229, 11th March 2000 [link]

In cross-country matches, teams consist of six runners. The team scores are decided by adding together the finishing positions of the first four runners to finish in each team. The team with the lowest score is the winner. Individuals never tie for any position and neither do teams because if two teams have the same score the winner is the team with the better last scoring runner.

The fifth and sixth runners to finish in each team do not score. However if they finish ahead of scoring runners in another team they make they make the scoring positions of those scoring runners, and the corresponding team score, that much worse.

In a recent match between two teams, I  was a non-scorer in the winning team. Each team’s score was a prime number, and if I told you what each team’s score was you could deduce with certainty the individual positions of the runners in each team. I won’t tell you those scores, but if you knew my position you could, with the information given above, again deduce with certainty the individual positions of the runners in each team.

(1) What was my position?
(2) What were the positions of the scoring runners in my team?

[enigma1073]

5 responses to “Enigma 1073: Cross-country match

  1. Jim Randell 26 February 2018 at 7:44 am

    This Python program runs in 90ms.

    Run: [ @repl.it ]

    from itertools import combinations
    from collections import defaultdict
    from enigma import irange, is_prime, diff, printf
    
    # positions
    pos = irange(1, 12)
    
    # record positions for teams A and B by their scores
    rs = defaultdict(list)
    
    # choose the finishing positions of winning team A
    for A in combinations(pos, 6):
      # the score is sum of the first 4 runners
      sA = sum(A[:4])
      if not is_prime(sA): continue
      # the remaining positions belong to the losing team B
      B = diff(pos, A)
      sB = sum(B[:4])
      if not is_prime(sB): continue
      # A wins
      if not(sA < sB or (sA == sB and A[3] < B[3])): continue
      rs[(sA, sB)].append((A, B))
    
    # find results where the scores uniquely indicate the individual positions
    # and record results by the positions of the non-scoring runners in team A
    ss = defaultdict(list)
    for ((sA, sB), vs) in rs.items():
      if len(vs) != 1: continue
      (A, B) = vs[0]
      printf("[A={sA}:{A}, B={sB}:{B}]")
      ss[A[-1]].append(A)
      ss[A[-2]].append(A)
    
    # find unique positions for the setter
    for (p, vs) in ss.items():
      if len(vs) != 1: continue
      A = vs[0]
      printf("p={p} -> A={A}")
    

    Solution: (1) You finished 8th; (2) The scoring runners in your team finished 2nd, 4th, 5th, 6th.

    The positions for the winning (setters) team were:

    2nd, 4th, 5th, 6th, 7th, 8th

    giving a total score of 17 (prime).

    The positions for the losing team were:

    1st, 3rd, 9th, 10th, 11th, 12th

    giving a total score of 23 (prime).

  2. Brian Gladman 26 February 2018 at 2:31 pm
    from itertools import combinations
    from collections import defaultdict
    from number_theory import is_prime
    
    # find teams of six runners by adding two non-scoring runners
    # to each team of four scoring runners with a prime score
    sp_to_tp = defaultdict(list)
    # consider four runners giving a prime score for the winning team
    for c4 in combinations(range(1, 13), 4):
      sc1 = sum(c4)
      if is_prime(sc1):
        # add two non-scoring runners
        for ns2 in combinations(range(max(c4) + 1, 13), 2):
          t1 = c4 + ns2
          # find the other team's positions and score
          t2 = tuple(x for x in range(1, 13) if x not in t1)
          sc2 = sum(t2[:4])
          if is_prime(sc2):
            # the winning team has a lower score
            if sc1 < sc2 or sc1 == sc2 and t1[3] < t2[3]:
              sp_to_tp[(sc1, sc2)].append((t1, t2))
    
    # now index winning team positions on the positions
    # of its non-scoring members 
    nsp_to_wps = defaultdict(list)
    for ab, tp in sp_to_tp.items():
      if len(tp) == 1:
        wp = tp[0][0]
        nsp_to_wps[wp[-1]].append(wp)
        nsp_to_wps[wp[-2]].append(wp)
        print(f'scores = {ab}, winning team positions = {wp}.')
    
    for mp, wps in nsp_to_wps.items():
      if len(wps) == 1:
        print('(Q1) {} (Q2) {}, {}, {}, {} ({}, {})'.format(mp, *wps[0]))
    
  3. Hugh Casement 26 February 2018 at 8:03 pm

    There are thirteen ways in which the scores 17 and 23 can be made up as the sum of four integers each, with no duplication; four of those ways do not use 8.  So I don’t see how either piece of information could determine the positions uniquely.  Please explain!

    • Jim Randell 26 February 2018 at 10:53 pm

      @Hugh: You might want to check again.

      You can’t have, for instance, team A = (1, 2, 4, 10) = 17 and team B = (3, 5, 6, 9) = 23, with (7, 8, 11, 12) being the non-scoring runners. As if runner 10 scored for A, then team A’s non-scoring runners would be 11 and 12, so B’s runners would be (3, 5, 6, 7, 8, 9), so their scoring runners would by (3, 5, 6, 7) not (3, 5, 6, 9).

      In fact there is only one possibility for A=17 and B=23.

      Similarly there are two other A, B scores that only have one possible assignment of positions.

      Then looking at the non-scoring runners for team A for each of these three scenarios, we find that there is a position that only appears in one of the possibilities, and that gives us the required answer.

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: