My professor gave the following question as a bonus, if two brothers Pat and Steve enter a rock paper scissors competition with $2^n$ players. In this competition players are randomly paired and then the winners move on to the next round. What is the probability that at one point in the competition the brothers face each other? My professor said my answer was wrong, and provided no explanation. I was wondering where my logic went wrong?
This is the solution I gave.
We can look at a smaller part of this problem to help solve the larger problem, the smaller part being what is the probability that two people will face each other in an individual round of of the tournament with $2^n$ players. This problem can also be expressed as the following, given a random pairing of $2^n$ people which includes two brothers Pat and Steve, what is the probability that the brothers will be in the same pair. This is given by the number of pairings where Pat and Steve are together divided by the total number of pairings. Notice that the number possible pairings where Pat and Steve are held constant is the number of pairings for $2n-2$ people. Thus if we can find some function $f(2n)$ that is defined as the number of ways of pairing $2n$ people, then the ratio $\frac{f(2^n-2)}{f(2^n)}$ will give us the desired probability. To find this ratio, lets consider how many pairings we add by increasing the number of people we are pairing by two. When this pair is held together there are $f(2n-2)$ pairings, and if we switch one of the people with a new person there are another $f(2n-2)$ pairings. If we hold one person constant we can pair him with any of the other $2n-1$ people. Since by summing these all together we get all of the possible pairings, this is $(2n-1)*f(2n-2)$. Thus the ratio we were looking for is $\frac{f(2^n-2)}{(2^n-1)*f(2^n-2)} = \frac{1}{2^n-1}$. The probability that both brothers reach the nth round is $\frac{1}{4^n}$, and since these cases are distinct from when the brothers face each other the probability that the brothers face each other in any of the $n$ rounds is the sum $\sum_{i=0}^n \frac{1}{2^{n-i}-1}*\frac{1}{4^n}$.