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]

Advertisements

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.

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: