# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1339: Quarter-final draws

From New Scientist #2498, 7th May 2005

Of the 8 fifth round games in this year’s FA cup competition 4 were won and 4 required replays. When the draw for the quarter-finals was made each game matched a team that had won against the winner of a replay.

(1) What as a fraction expressed in its lowest terms was the probability that the draw would produce this outcome?

(2) What was the probability (similarly expressed) that it would produce two games that involved the four teams that had won and two that involved the winners of the four replays?

[enigma1339]

### 3 responses to “Enigma 1339: Quarter-final draws”

1. Jim Randell 17 March 2014 at 7:30 am

This is a bit similar to Enigma 1344, in that they are both about pairing up members of distinct sets. This Python program constructs all parings (using the partitions() function from enigma.py, originally created for Enigma 1449 but useful in several puzzles) and counts how many satisfy the conditions for each part of the problem. It runs in 54ms

```from fractions import Fraction as F
from enigma import partitions, printf

# divide the teams into the two sets
W = set((1, 2, 3, 4))
R = set((5, 6, 7, 8))

# count pairs that match the two conditions in the puzzle
n1 = n2 = N = 0
for ps in partitions(W.union(R), 2):
N += 1

# part 1: each team has an element from both sets
if all(W.intersection(p) and R.intersection(p) for p in ps):
n1 += 1

# part 2: each team has elements from only one of the sets
if all(not(W.intersection(p)) or not(R.intersection(p)) for p in ps):
n2 += 1

(p1, p2) = (F(n1, N), F(n2, N))
printf("p1 = {p1}, p2 = {p2} [n1={n1}, n2={n2}, N={N}]")
```

Solution: (1) 8/35; (2) 3/35.

• Jim Randell 17 March 2014 at 7:40 am

Here is a program that determines the solution analytically. I used the pairs() function from my solution to Enigma 1344. It agrees with the solution produced by the constructive approach and runs in 51ms.

```from fractions import Fraction as F
from enigma import C, factorial, printf

# the 8 teams in the quarter finals are divided into two distinct sets:
# R - teams that won after a replay
# W - teams that won without a replay

# the number of different pairs from 2k items
def pairs(k):
# choose k items and pair them with the remaining k items, and remove duplicates
return C(2 * k, k) * factorial(k) // (2 ** k)

# total number of outcomes
N = pairs(4)

# part 1 - each match has a pair from R and W

# for each team in R we choose a remaining team in W

p1 = F(factorial(4), N)
printf("p1 = {p1}")

# part 2 - each match has both sides in one of R or W

# for a set with 4 teams in we can pair team 1 with any of the
# remaining 3 teams, and the other two teams form a pair

# and there are two sets of 4 teams.

p2 = F(3 ** 2, N)
printf("p2 = {p2}")
```
2. Jim Olson 20 March 2014 at 1:41 am

This enigma is much easier and quicker to do just by analysis.