Enigmatic Code

Programming Enigma Puzzles

Enigma 1169: Snookered

From New Scientist #2325, 12th January 2002 [link]

George lives not far from the Crucible Theatre, where the annual World Snooker Championship has been held for the past 25 years. Each year 32 players compete in a straightforward knockout tournament to determine who is the champion.

George, and his brother Fred, have entered a less prestigious tournament at their local pub. Since they cannot be certain that the number of entrants will be a power of two, lots will be drawn to see who is awarded byes in the first round. The tournament will then continue as a knockout, also drawn at random.

While waiting for the draw to be made, George calculated the chance that he will at some stage have to play against his brother, assuming all the players are of equal ability. It is exactly one in ten.

How many players entered the tournament?

[enigma1169]

Advertisements

One response to “Enigma 1169: Snookered

  1. Jim Randell 2 May 2016 at 8:22 am

    For each match in a knockout tournament one player is eliminated, until there is only one player left. So for a tournament with n players, there are n − 1 matches required to determine the winner.

    The total number of possible pairings from n players is: C(n, 2) = n(n − 1) / 2

    And one of these pairings will be the required pairing of George and Fred.

    So (assuming all outcomes are equally likely) the probability of George playing Fred in any of the matches for a tournament with n players is:

    P(n) = (n − 1) / (n(n − 1) / 2) = 2 / n

    We are interested in the case where: P(n) = 1/10

    2 / n = 1 / 10
    ⇒ n = 20

    Solution: 20 players entered the tournament.

    Because I’m never too sure of my analysis with probabilities, and because I like to have a constructive solution (and to write a program), here’s a Python program that runs simulated tournaments with n players and counts the number of times two specific players play each other. The byes are allocated at random, and the remaining players paired up into matches at each round until there is only one player remaining. The number of tournaments where the specific players meet is then compared with the expected probability, as determined above.

    The program runs 1,000,000 trials for n between 2 and 32 in 1m13s, and finds that the results do indeed match the predicted values (to 3 decimal places).

    import random
    from itertools import count
    from enigma import cached, irange, printf
    
    # number of byes for a tournament with n competitors
    @cached
    def byes(n):
      return (0 if (n & (n - 1)) == 0 else byes(n + 1) + 1)
    
    # pop a random item from a list
    def pop(s):
      e = random.choice(s)
      s.remove(e)
      return e
    
    # trial with n competitors
    # returns: "does player 1 play against player 2?"
    def trial(n):
      # the players in this round
      ps = list(irange(1, n))
      # give some of the players byes
      ws = list()
      for _ in irange(1, byes(n)):
        ws.append(pop(ps))
      # now play the round
      p = len(ps)
      while p > 1:
        # play the matches
        for _ in irange(1, p // 2):
          w = pop(ps)
          l = pop(ps)
          if (w == 1 and l == 2) or (w == 2 and l == 1): return 1
          ws.append(w)
        # are both players still in the game?
        if not(1 in ws and 2 in ws): return 0
        # get ready for the next round
        ps = ws
        ws = list()
        p = len(ps)
      # we're done
      return 0
    
    # number of trials
    N = 1000000
    
    # consider increasing n
    for n in irange(2, 32):
      # run the trials
      t = sum(trial(n) for _ in irange(1, N))
      f = float(t) / float(N)
      s = ('*** SOLUTION ***' if abs(1.0 - f / 0.1) < 0.01 else '')
      printf("n={n} f={t}/{N}={f:.3f} (expected {x:.3f}) {s}", x=2.0 / n)
    

    The function to calculate the number of byes is taken from my solution to Enigma 176.

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: