In a certain contest, the players are of equal skill and the probability is 1 2 that a specified one of the two contestants will be the victor, in a group of 2 n players, the players are paired off against each other at random. The 2 n − 1 winners are again paired off randomly, and so on, until a single winner remains. Consider two specified contestant, A and B, and define the events A i , i ≤ n , E by A i :

A plays in exactly i contests

E: A and B never play each other

1. Find P ( A i ) , i = 1 , ... , n .
2. Find P ( E ) .
3. Let P n = P ( E ) .
4. Show that P n = 1 2 n − 1 + 2 n + 2 2 n − 1 ( 1 2 ) 2 P n − 1 are use this formula to check the answer you obtained in part (b).

Hint: Find P ( E ) by conditioning on which of the events P ( A i ) , i = 1 , ... , n occur. In simplifying your answer, use the algebraic identity ∑ i = 1 n − 1 i x i − 1 = 1 − n x n − 1 + ( n − 1 ) x n ( 1 − x ) 2

For another approach to solving this problem, note that there are a total of 2 n − 1 games played.

1. Explain why 2 n − 1 games are played.

Number these games, and let B i denote event that A and B play each other in game i , i = 1 , ... , 2 n − 1 .