The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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.

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

- Doctor Anthony, The Math Forum   
Associated Topics:
High School Probability

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.