Thursday, April 27, 2006

Second best as runner up

Let us take a little turn today - Probability! Lets try a question on chance in a tennis match. There are 8 players for a tennis tournament. They are to play in pairs with one other player in the first round and the winners play in the next round and so on until we have a winner and a runner up. There is a player amongst these 8 who is the best and the odds of him winning the tournament is very high. There is another player who is considered the second best. The players draw numbers to take on their counter players for the first round. What is the chance (probability) that the second best player can be the runner up when the tournament is over? Once you get the probability, work a generic mechanism to find the chance for a 'm' player tournament. Substitute m = 8 in that equation and see if you get the same answer as you worked out.

Level: Easy to Medium

10 Comments:

Anonymous Anonymous said...

3/4*1/2 = 3/8
Product (k-1)/k for k=m/2 to 2

10:53 PM, April 27, 2006  
Anonymous Anonymous said...

oops .. for k=m/2 to 2 ;k=k/2

10:54 PM, April 27, 2006  
Blogger Avianwing said...

It is 4/9 probability for player S to meet player B(best) in the final, if it is a knockout tournament. But i suspect it is not. If m>8 , the number of rounds will be log(base2)m -1. Can't think of the formula immediately.

11:14 PM, April 27, 2006  
Anonymous Anonymous said...

we have to make sure that the FIRST and SECOND player end up in separate halves of the 1st round of players.

is it (n-2)C(n/2-1)/nC(n/2) ?

nC(n/2) are the possible combinations for forming a group with half the players.

since f and s are to be excluded. there are only n-2 players who can be placed in the 1st half or second half where only 1 less than half the positions remain undecided.

in this case 2/7.

11:37 PM, April 27, 2006  
Blogger Karthik Nagaraj said...

Wow, so many replies from anonymous folks out there ;). Lets see the replies one by one

[1] 3/8 -> is wrong, the genetic formula is not correct
[2] 4/9 -> is not correct
[3] the formula looks a little complicated and since you say it is 2/7 -> it is not correct

Ok, coming to the clarification of it being a knockout round - it is true that this is a knockout round, that's why the problem clearly tells us "They are to play in pairs with one other player in the first round and the winners play in the next round and so on until we have a winner and a runner up". This means that every player will play with only one other player in the first round. So after the 1st round we will have 4 winners. These 4 winners again play. Much like the tennis tournaments, don't confuse it with cricket tournament where they have to play with every other team. Each player plays with his/her opponent only once. So now the 2nd round will have 2 matches and that will decide who will go into the finals - and finally one winner and one runner up. Hope the question is more clear now.

12:39 AM, April 28, 2006  
Blogger Avianwing said...

Is it 18/28

1:33 AM, April 28, 2006  
Blogger Karthik Nagaraj said...

18/28 -> Sorry it is not correct. Let me give you a clue. There are 8 players in the tournament. So there will be 4 matches in the first round. Out of this there will be 4 winners. Again there will be 2 matches in the 2nd round, out of which we will have 2 winners. These 2 will play in the final. Now the questions says what is the probability that the second best player will be the runner-up in the tournament? Did I hear someone tell "we have to make sure that the FIRST and SECOND player end up in separate halves of the 1st round of players." Try it out.

6:25 AM, April 28, 2006  
Anonymous Anonymous said...

It is 4/7
Chance that seeds 1 and 2 play in the final is given by m/2(m-1)
if m = 8, P = 4/7.

my logic is like this.
Seeds 1 and 2 should appear in different halves of the pool to avoid meeting until the final. so we choose a slot in the top half for seed1 and bottom half for seed 2.
the remaining players fit in (m-2)! ways.

P = (m/2)(m/2)*(m-2)!/m! * 2(as seed1 and 2 can be interchanged)

P = m/2(m-1)

7:20 AM, April 28, 2006  
Anonymous Anonymous said...

I think that Vikram is right. Sad that I am a couple of minutes late!!!

7:21 AM, April 28, 2006  
Blogger Karthik Nagaraj said...

Vikram, you got a bulls eye. But there is a more simpler explanation to this than using factorials. Let me elucidate it here:

We have 8 players - so 8 places can be occupied. We know one is seed 1 and other is seed 2 and they cannot be in the same half of the tree - so the seed 2 can only occupy the other half tree that the seed 1 has not occupied. So that leaves him/her to get into any of the 4 places. Since we have to fix seed 1's position to decide the seed 2, there are a total of 8-1=7 places for all the others. So probability that the seed 2 will meet seed 1 in the finals will be 4/7

To get a more generic method, draw a tree that tries to mimic the match scenario. to play this kind of a knockout series you need to have a multiple of 2^n # of players. In this case 2^n = 8 (n=3). So total # of places all the others can occupy if the position of seed is decided is
2^n - 1
Now, we know that seed 1 and seed 2 cannot be in the same half tree. So that leaves us the # of ways the seed 2 can be arranged is (2^n)/2

Hence probability is

[(2^n)/2]/(2^n - 1) = m/2(m-1)

Exactly, what is got from Vikram's answer. Good thinking guys! Avianwing had come very close to getting the right answer. So this puzzle is SOLVED!

8:07 AM, April 28, 2006  

Subscribe to Post Comments [Atom]

<< Home