Enigmatic Code

Programming Enigma Puzzles

Enigma 1276: Multiple byes

From New Scientist #2434, 14th February 2004

In modern knock-out events any byes that are needed are all given in the first round, but at the ancient Olympics all the competitors took part in the first round unless there was an odd number, in which case one drew a bye and joined the winners in the next round. This system was used in each subsequent round until there were two finalists. Even the semifinals might involve only three competitors, of whom one drew a bye into the final.

I think this system should be revived for one of the events at this years Olympics in Greece. One of the British competitors could draw the bye in every round and thus reach the final without ever beating anybody! But the odds against Britain getting a finalist in the event by these means are very nearly a million to one.

How many competitors are there in the event, and how many of them are British?

[enigma1276]

One response to “Enigma 1276: Multiple byes

  1. Jim Randell 23 November 2014 at 8:38 am

    Odds of a million to one are a probability of 1/1000001.

    In order for there to be a bye at each round there must be 2^n + 1 players in the first round.

    The chance of any particular player getting the bye in the first round is 1/(2^n + 1).

    The chance they also get the next bye is 1/(2^(n − 1) + 1).

    And so on, all the way through to a 1/3 chance they get the bye in the semi-final.

    So the probability of any particular player getting all the byes is:

    p = 1/3 × 1/5 × 1/9 × 1/17 × … × 1/(2^n + 1)

    But we don’t care which Brit makes it through to the final in this way, so if there are b Brits, out of the 2^n + 1 players in the first round, then the probability of one of them getting all the byes is:

    b × p

    and we want this to be as close to 1/1000001 as possible.

    This Python program examines the possible values. It runs in 50ms.

    from fractions import Fraction as F
    from itertools import count
    from enigma import irange, Accumulator, printf
    
    r = Accumulator(fn=min)
    
    p = 1
    for i in count(1):
      # number of players
      n = 2 ** i + 1
      # probability of getting all the byes
      p *= F(1, n)
      # required number of brits
      b = F(1, 1000001 * p)
      printf("[i={i} n={n} p={p} b={b:f}]", b=float(b))
      if b > n: break
      # turn it into a reasonable number
      b = min(max(int(b + F(1, 2)), 1), n)
      t = b * p
      r.accumulate_data(abs(t - F(1, 1000001)), (n, b, t))
    
    # output the best value
    (n, b, t) = r.data
    printf("{n} players, {b} brits, probability = {t}")
    

    Solution: There were 65 competitors. 5 of them were British.

    In fact there is only one possibility, which is when there are 65 players (n=6). The probability of any single player getting all the byes is 1/4922775. The denominator being close to 5 million, so if there were 5 Brits in the first round the probability of any one of them getting all the byes would be close to 1 in 1000000.

    The actual probability is 1/984555, or odds of 1 in 984556.

    For smaller values of n the probability is more than 1/1000001, so would require a fractional Brit.

    For larger values of n the probabilities are so small it would require more Brits than there are players to get close to 1/1000001.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: