Problem of the Week 1162

A World Cup Problem

Solution

Problem 1162 was solved by Rob Pratt, Dave Ehren, and Barry Cox.

Pratt writes: Imagine that the eight group names are written four times each on 32 slips of paper and placed in a hat. Each team, one at a time, selects a slip out of the hat, with the four superior teams 1, 2, 3, and 4 selecting first.

For i = 2, 3, 4, let Ei be the event that team i selects a group distinct from teams 1 to i - 1. Then the desired probability is:

Prob(E2) Prob(E3 given E2) Prob(E4 given E3 and E2)
= (28/31) (24/30) (20/29)
= 448/899
~ 0.498

Four incorrect solutions were received: three had the wrong fractions. One did a simulation and concluded that the result was likely equal to 1/2 exactly; it is not. One person did a simulation that confirmed a certain incorrect result, but the simulation was based on the same faulty reasoning.

So there is a moral there about simulations, which should try to be completely removed from the method that one is trying to confirm.

The problem is similar to the birthday problem, but not the same since in that problem there is no limit on how many people can have the same birthday. If we think of the 8 groups as birthdays and assign them randomly to the 32 teams, the chance that the "birthdays" of the superior four teams are all different is:

(7/8) (6/8) (5/8) = (28/32)(24/32)(20/32) = 41%

Barry Cox observes that a general formula can be given an alternate form as follows: Suppose there will be m groups of n teams each and p teams are considered elite, where p ≤ m. The probability that the elite teams are separated is

Binomial[m,p] n^p / Binomial[n*m, p]

[Back to Problem 1162]

© Copyright 2013 Stan Wagon. Reproduced with permission.


9 September 2013