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}$.

  • 3
    $\begingroup$ Actually, I got lost in your argument. A $2^n$ player knock-out tournament consists of $2^n-1$ matches with all pairings distinct. Since there are $2^n\choose 2$ pairings in total, the probability for a given pairing to occur among the pairings actually taking place, is $$\frac{2^n-1}{2^n\choose 2}=2^{1-n} $$ $\endgroup$ – Hagen von Eitzen Dec 12 '12 at 22:28
  • 1
    $\begingroup$ Suppose the two brothers are losers. Then they can only meet in the first round. So we need to make assumptions, maybe that in any game, a player wins with probability $1/2$, and that all results are independent. $\endgroup$ – André Nicolas Dec 12 '12 at 23:16
  • $\begingroup$ @Hagen: +1 and to generalise your answer more fully, if there are $k$ randomly distributed in a knockout competition with random winners, the probability any particular pair will meet is $\frac{2}{k}$ $\endgroup$ – Henry Dec 13 '12 at 1:17

Your result $f(n)=(2^n-1)f(2^n-2)$ is correct (though it could have been more easily derived by noting that a player is equally likely to be paired with any of the $2^n-1$ other players). Note that you wrote $2n$ instead of $2^n$ in several places.

Your final result is wrong on several counts: It should say $4^i$ instead of $4^n$; the sum should only run up to $n-1$; and you didn't take into account that the later stages are only reached if the two aren't paired before, e.g. the second term isn't




The first numerator and second denominator cancel up to a factor $2$, and the same for subsequent terms, so the correct sum is

$$ \sum_{i=0}^{n-1}\frac1{2^n-1}\frac1{2^i}=\frac1{2^n-1}\frac{1-(1/2)^n}{1-(1/2)}=2^{1-n}\;, $$

consistent with the result that Hagen derived by a more elegant argument in a comment.

  • $\begingroup$ Ahh. I did make some mistakes typing it, sorry about that. Thanks a bunch $\endgroup$ – user52869 Dec 13 '12 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy