4

In a knockout tournament $2^n$ equally skilled players;$S_1,S_2,...,S_{2^n}$ are participating.In each round players are divided in pair at random and winner from each pair moves in the next round.If $S_2$ reaches the semi-final then the probability that $S_1$ wins the tournament is $\frac{1}{20}$.Find the value of $n.$

There will be $n$ rounds of the tournament because $2^n$ players are there.But i dont know how to solve further.Some help/hints are needed.Thanks.

diya
  • 3,589
  • 2
    Why did you set a bounty for this? Did you try to apply the hints that Ross and I provided? – joriki Oct 10 '15 at 05:53
  • Sir,I tried but still could not get the answer.I appreciate your hints but i could not solve it.@joriki – diya Oct 11 '15 at 10:11

2 Answers2

10

There isn't enough information to answer the question, since we don't know the probabilities of the players winning their games. I'll assume that the outcomes of all games are independent and either player has a $50\%$ chance of winning each game.

The probability that $S_2$ will win is $\frac14$. If she doesn't, every other player has the same chance.

Edit:

Here's a more explicit solution. The probability that $S_2$ will win is $\frac14$, since she reached the semifinal. Thus the probability that someone else will win is $\frac34$. No-one else is special, so they all have the same probability to win. Since there are $2^n-1$ of them, the probability that one of them, $S_1$, wins is $\frac34\left(2^n-1\right)^{-1}$. Equating this to $\frac1{20}$ then yields $n$.

joriki
  • 238,052
  • Its answer is given $n=4$ in the book.@joriki – diya Oct 04 '15 at 05:17
  • @diya: Yes, that's the correct answer. Not sure what you're trying to tell me with that? – joriki Oct 04 '15 at 05:18
  • Cant the value of $n$ be found with the given information in the question. – diya Oct 04 '15 at 05:20
  • 2
    @diya: No, as I wrote, it can't (if you copied the question completely and correctly). But it can be found with the additional assumption that I made. It seems likely that the book was merely negligent in forgetting to add that assumption. If you make that assumption, you can find $n$ using the hint I provided. – joriki Oct 04 '15 at 05:21
  • @joriki: How does "If $S_2$ reaches the semi-final then the probability that $S_1$ wins the tournament is $\frac{1}{20}$" fit in ? – true blue anil Oct 04 '15 at 08:44
  • @trueblueanil: I gave a hint how to calculate the probability that $S_1$ wins the tournament under the condition that $S_2$ reaches the semi-final. If you can calculate that, you can equate it to $\frac1{20}$ to find $n$. – joriki Oct 04 '15 at 08:46
  • You have missed the point that $S_2$ is not at risk of reaching the semifinal from any player not in her quarter of the draw. $S_1$ must be in another quarter of the draw. – Ross Millikan Oct 12 '15 at 03:58
  • @RossMillikan: I don't understand -- you gave the same answer, with a similar justification -- in what sense have I missed a point? I don't see how the fact that $S_1$ must be in another quarter of the draw (which is obviously true) invalidates any part of my argument. – joriki Oct 12 '15 at 04:45
7

Hint: Four players reach the semi-final, each the winner of a tournament of $2^{n-2}$ players. $S_1$ cannot be in the same bracket as $S_2$, but is a random participant from the other three brackets.

Added: The chance that $S_1$ gets to the semis is $\frac 3{2^n-1}$ because the semi participants besides $S_2$ are chosen at random from the pool. The chance that $S_1$ wins is then $\frac 3{4(2^n-1)}=\frac 1{20}$, so $n=4$

Ross Millikan
  • 374,822