**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]

### Like this:

Like Loading...

*Related*

This Python program runs in 48ms.

Solution:There were 18 teams at the start of the draw.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.

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?

The best expression I can get for the

nth term in the sequence of products is: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.

1/t[n]exceeds 100 atn=10 and it just under 100 atn=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.

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.