68. In a knockout tennis tournament of 2n contestants, the players are paired and play a match. The losers depart, the remaining 2n−1 players are paired, and they play a match. This continues for n rounds, after which a single player remains unbeaten and is declared the winner. Suppose that the contestants are numbered 1 through 2n, and that whenever two players contest a match, the lower numbered one wins with probability p. Also suppose that the pairings of the remaining players are always done at random so that all possible pairings for that round are equally likely.

(a) What is the probability that player 1 wins the tournament?

(b) What is the probability that player 2 wins the tournament?

Hint: Imagine that the random pairings are done in advance of the tournament.

That is, the first-round pairings are randomly determined; the 2n−1 first-round pairs are then themselves randomly paired, with the winners of each pair to play in round 2; these 2n−2 groupings (of four players each) are then randomly paired, with the winners of each grouping to play in round 3, and so on. Say that players i and j are scheduled to meet in round k if, provided they both win their first k − 1 matches, they will meet in round k. Now condition on the round in which players 1 and 2 are scheduled to meet.