### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,959 hits

Advertisements

Programming Enigma Puzzles

23 July 2014

Posted by on **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

%d bloggers like this:

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.

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