Enigmatic Code

Programming Enigma Puzzles

Enigma 1307: KO, OK?

From New Scientist #2465, 18th September 2004

Sixteen players numbered 1 to 16 entered a men’s knockout tennis tournament. In each round the numbers of the remaining players were drawn at random to decide who played whom.

At the end of the tournament each player wrote down the number or numbers of the players he had competed against, in the order in which he had played them. The lists of the two finalists had their numbers in increasing order.

Also, each player worked out the total of the numbers in his list. The highest total was four times the lowest.

Which two players were in the final?

[enigma1307]

Advertisements

One response to “Enigma 1307: KO, OK?

  1. Jim Randell 23 July 2014 at 7:59 am

    Considering all possible permutations of 16 is clearly going to take a long time. So in this program I choose the two ascending sequences of 4 players that are the opponents of the finalists, and then permute the remaining 8 players. The runtime is further improved by checking the opponent sums of the 8 players we already know and if the maximum is already greater than 4 times the minimum we reject the candidate solution and don’t bother permuting the final 8 players.

    This Python program runs in 6.3s.

    from itertools import combinations, permutations
    from collections import Counter
    from enigma import irange, diff, printf
    
    players = list(irange(1, 16))
    
    # count the results
    r = Counter()
    
    # B, C, E, I are in order
    for (B, C, E, I) in combinations(players, 4):
      ps1 = diff(players, (B, C, E, I))
      # J, K, M, A are in order
      for (J, K, M, A) in combinations(ps1, 4):
        ps2 = diff(ps1, (J, K, M, A))
        # check sums we already know
        ss0 = (
          B + C + E + I,
          A,
          C,
          E,
          J + K + M + A,
          I,
          K,
          M,
        )
        if 4 * min(ss0) < max(ss0): continue
        # assign the remaining players
        for (D, F, G, H, L, N, O, P) in permutations(ps2):
          # sums of opponent numbers
          ss = ss0 + (
            D + A,
            F + G + A,
            H + E,
            G,
            L + I,
            N + O + I,
            P + M,
            O
          )
          if 4 * min(ss) != max(ss): continue
    
          r[(min(A, I), max(A, I))] += 1
          printf("A={A} I={I} [{A} {B} {C} {D} {E} {F} {G} {H} {I} {J} {K} {L} {M} {N} {O} {P}] max={max} min={min}", max=max(ss), min=min(ss))
    
    for (k, v) in r.items():
      printf("final is {k} [{v} solutions]")
    

    Solution: The final was played between player 13 and 14.

    The maximum opponent sum is 36, the minimum opponent sum is 9.

    My program finds 5760 separate solutions, although we can appeal to symmetry to reduce these (e.g. requiring A < I, cuts it down by a factor of 2).

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: