Enigmatic Code

Programming Enigma Puzzles

Enigma 1264: Unlucky draw

From New Scientist #2420, 8th November 2003

It was time to make the draw for a knockout stage in the cup. To make it easy for viewers to spot the most interesting match-ups, every team left in the competition was allocated a ball: white if they were in division 1 of the league and black if they were in division 2. As it happened, there were an equal number of black and white balls in the velvet bag at the start. The format of the draw was to pick out at random two balls at a time — these two teams would play each other — until there were no balls left.

As the draw progressed, the various team representatives couldn’t help but notice that the matches were consistently between one team from division 1 and one team from division 2. In fact, when the draw was complete this was true of every single match. The representatives of the division 2 teams were furious and claimed [that the odds of this happening by chance] were only a tiny bit better than 1 in 100.

How many teams were in the cup at the start of the draw?

I don’t have a complete source for this puzzle, so I’ve guessed at the wording in square brackets. It seems to make sense as a question and matches the answer given in the magazine.

If anyone has the complete text, or (even better) an image of the puzzle in New Scientist, please get in touch.

[enigma1264]

Advertisements

5 responses to “Enigma 1264: Unlucky draw

  1. Jim Randell 11 January 2015 at 8:15 am

    This Python program runs in 48ms.

    # if there are n teams from each division then the probability of two
    # teams from different divisions being chosen are n / (2n - 1).
    #
    # then there are (n - 1) teams from each division left.
    #
    # so we consider the product of increasing n / (2n - 1) terms
    
    from itertools import count
    from fractions import Fraction as F
    from enigma import printf
    
    from itertools import count
    from fractions import Fraction as F
    from enigma import printf
    
    t = 1
    for n in count(1):
      s = F(n, 2 * n - 1)
      t *= s
      printf("[n={n} s={s} t={t} ({f:.3f})]", f=float(t))
      if 100 * t < 1: break
    
    teams = 2 * (n - 1)
    printf("{teams} teams")
    

    Solution: There were 18 teams at the start of the draw.

  2. Hugh Casement 11 January 2015 at 11:29 am

    So the numerator is n! and the denominator is the product of all the odd numbers up to (2n – 1).
    Is there an expression for that, akin to Stirling’s formula for n! ?
    That should allow one to determine the probability quickly for any n.
    It’s something like exp(1.06 – 0.62 n), but that’s only a rough approximation.

    • Hugh Casement 11 January 2015 at 11:51 am

      Not quite awake just now. The product of all the odd numbers up to (2n – 1) would appear to be (2n)! divided by n! 2^n (which is the product of all the even numbers up to 2n).
      So the inverse of the probability that we’re looking for is that divided by a further n!.
      For n = 9 it works out at about 94.96. Does that figure?

      • Jim Randell 12 January 2015 at 12:51 pm

        The best expression I can get for the nth term in the sequence of products is:

        t[n] = 2^(n – 1) / C(2n – 1, n)

        which doesn’t really help me spot when t[n] becomes less than 1/100.

        So I think the best approach (either manually or programmatically) is to start calculating them, and accumulate the product rather than calculate it directly.

        As you point out, when doing it manually it’s probably easier to consider the inverse of the product, and see when it exceeds 100.

         n   1/s[n]        1/t[n]        2dp
        
         1   1/ 1          1/      1    1.00
         2   3/ 2          3/      2    1.50
         3   5/ 3         15/      6    2.50
         4   7/ 4        105/     24    4.38
         5   9/ 5        945/    120    7.88
         6  11/ 6      10395/    720   14.44
         7  13/ 7     135135/   5040   26.81
         8  15/ 8    2027025/  40320   50.27
         9  17/ 9   34459425/ 362880   94.96
        10  19/10  654729075/3628800  180.43

        1/t[n] exceeds 100 at n=10 and it just under 100 at n=9, so the solution is that when there are 9 teams in each division (so 18 teams overall), then the odds of every match being between teams in different divisions is just under 100-1 (actually very close to 94-1).

        My program follows the same steps.

        • Hugh Casement 14 January 2015 at 9:18 am

          We seem to be getting the same results, in spite of a slightly different way of looking at it.
          I think you’ll find my expression for the reciprocal probability works:
          (2n)! divided by (n!)² 2^n.
          Using Stirling’s formula one can approximate it as 2^n / sqrt(pi n),
          though for small values of n it might be better to take 3.25 rather than pi.
          However, I agree that doesn’t help much because we can’t readily invert it to give an expression for n as a function of p.
          So, as you say, we do best to accumulate the product step by step.

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: