Combinatorial Probability Tournament

Date: 01/23/2002 at 10:57:16
From: penina smith
Subject: Combinatorial probability tournament 

Here's the problem:

A tennis tournament for 2^n players is organised as a knock-out 
tournament with n rounds, the last round being the final. Two players 
are chosen at random. Calculate the probabilities they meet 

a) in the first round
b) in the final
c) in any round

(Hint: Can the same sample space be used for all three calculations?)

I tried looking at different cases, i.e. n=1, n=2, n=3, but cannot 
seem to provide a sound answer (with a sound argument) as to the 
probabilities for general n.

I hope you can help.
Regards,
Penina

Date: 01/23/2002 at 12:05:40
From: Doctor Anthony
Subject: Re: Combinatorial probability tournament 

Take a simple example to illustrate the method. Suppose there are 
8 players. The probability that A and B play each other is 1/7 in the 
first round. But a general approach to the problem is as follows:  

By symmetry, there are C(8,2) = 28 possible pairs.

The number of actual pairs that meet is  4 in 1st round
                                         2 in 2nd round
                                         1 in last round
                                        -----------------
                                Total  = 7

The probility they meet in the 1st round = 4/28 = 1/7

The probability they meet in the second round = 2/28 = 1/14

The probability they meet in the last round = 1/28

The probability that AB is one of the pairs that meet is  7/28  = 1/4

If there are 2^n players, the same reasoning for the probabilities is


a) in the first round.  Probability = 2^(n-1)/C(2^n,2)
b) in the final round.  Probability =  1/C(2^n,2)
c) in any round

The numerator of the probability will be

   1 + 2 + 4 + 8 + .... + 2^(n-1) = 2^n - 1

                          2^n - 1
So required probability  ---------
                          C(2^n,2) 

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/