# 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]

### 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).

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