Match Up

Topic

New Reply

64 people enter a knockout tournament. The first round consists of 32 matches between 2 competitors. The 32 winners progress to the second round. The second round consists of 16 matches between 2 competitors – the 16 winners progress to the third round. Etc Etc until only 1 competitor is undefeated.

If the 64 competitors are of roughtly equal ability and the opponents in each round are randomly selected, what is the probability that competitor A will compete against competitor B during the tournament?

Reply | Quote

Replies

1 in 32 (or 3.125 %)

Reply | Quote

That is not the answer that I have. Isn’t that the answer that they will meet in the first round? What about the possibility that they meet in the second, third, etc rounds?

Reply | Quote

I did take the 2nd, 3rd etc. rounds into account, but apparently my calculation is different from yours. Let’s see what others make of it.

Reply | Quote

Ok, I’ve reviewed my solution and I think I have found a hole. The new way I have worked out if they meet in the first round is …

Divide the 64 into two equal groups (G1 and G2) of 32. Place one person from G1 to matches 1 to 32 so that each match has one competitor. Randomly allocate one person from G2 to each match. Now, the four equally likely outcomes from the division into two groups is …

1. A in G1, B in G1
2. A in G1, B in G2
3. A in G2, B in G1
4. A in G2, B in G2

The probability that A will meet B in round 1 under 1) and 4) above is zero. The probability that A will meet B in round 1 under 2) and 3) above is 1/32. Thus the total probability that A will meet B in round 1 is 1/2 x 0 + 1/2 x 1/32 = 1/64

Hans – is that the answer you got for meeting in round 1?

Reply | Quote

My calculation for the 1st round was A has 64-1 = 63 potential opponents in the first round, so the probability of playing against B is 1/63.

Reply | Quote

yup – I’ve just run a simulation (500,000 trials) and it supports 1/63 more than 1/64 – wonder where the new hole in my thinking is?

Reply | Quote

I get the same answer as Hans:

Round	Prob	Calc
1	1.587%	=1/63
2	0.794%	=62/63/4/31
3	0.397%	=62/63/4*30/31/4/15
4	0.198%	=62/63/4*30/31/4*14/15/4/7
5	0.099%	=62/63/4*30/31/4*14/15/4*6/7/4/3
6	0.050%	=62/63/4*30/31/4*14/15/4*6/7/4*2/3/4
Total	3.125%

Reply | Quote

Not only the same answer, exactly the same calculation too!

Reply | Quote

I only knew the answers were the same, I had no way of knowing how you did the calculations.

I know when I helped my daughter with her homework, we always compared answers, never calculations. I always seemed to do it differently than she was and differently than the way the teacher showed them. It just confused her when she tried to learn my way, so we just compared work when the answers were different…

Steve

Reply | Quote

Do you need to take into account the apparent(?) 50% chance that either A or B will get knocked out?

Reply | Quote

Yep, that’s the /4 that occurs repeatedly: the chance that both A and B will make it to the next round is 1/2 * 1/2 = 1/4

Reply | Quote

Ah! – that answers my next question then

Reply | Quote

I worked this out a bit differently, but it seems to give the same answer…

In each round the chance of both remaining in the tournament is
1/1 (a certainty in round 1), 1/4, 1/16, 1/64, 1/256, 1/1024 (for round 6)
In each round the chance of them meeting, if they are still both in is
1/63, 1/31, 1/15, 1/7, 1/3, 1/1 (a certainty in round 6)
So the total ods of them meeting is
(1 * 1/63) + (1/4 * 1/31) + (1/16 * 1/15) + (1/64 * 1/7) + (1/256 * 1/3) + (1/1024 * 1)
which gives a result of 3.2615%

StuartR

Reply | Quote

[indent]

---

but it seems to give the same answer…

---

[/indent]

When has 3.2615% been equal to 3.125%?

Steve

Reply | Quote

Your number seem high to me (based on my calcs) since if they meet in later rounds, you have not eliminated the probability that the did NOT meet in an earlier round. You need to “preface” each of your calcs for the round to remove the odds of them meeting early.

For example, in round 2 you have: (1/4 * 1/31) but for them to meet in round 2 they must not have met in round 1 so your number needs to multiply by the odds of not meeting in round 1 so the round 2 number should be: 62/63 * 1/4 * 1/3 = 62/63/4/31

Steve

Reply | Quote

Woops, thank you, missed that detail.

StuartR

Reply | Quote

15.625%

Reply | Quote

With two highly respected sources both saying 1/32 and offering input on other solutions that would yield 1/32 – then we should accept 1/32 as the ANSWER. I’m still at a loss to work out what is wrong with my reasoning in post 523,791 – I think it has something to do with the assumption that the 4 cases each have a 1/4 probability.

Reply | Quote

I am not sure I understand your logic. Where do you get the 1/32?

I get for your Case 1 and 4 a 24.60% prob and for case 2 and 3 a 25.40% prob. They are not all equal probabilities. post 523,845[/url] continue the logic.

Steve

Reply | Quote

Steve – Sorry, but I don’t think that I was clear. The answer to the original question (as provided by Hans and you) is 1/32. The post that I quoted was trying to answer the probability that they meet in the first round. Hans (and you) were saying 1/63 which sounds very reasonable to me.

In post 523,791 – I was trying to come at the answer by a different route – I divided the contestants into two groups BEFORE the matches – if you think of the matches being held on 32 courts, the the each member in G1 would just go to any old court (it makes no difference). Then each player in G2 is randomly assigned to a court where they meet their opponent. Now, if each outcome (1, 2, 3 or 4 from post 523,791) has an equal probability, then the chance of A meeting B is 1/64. As I said, I don’t think that my assumption that each outcome has an equal probability of 25% is correct. How did you work out the prob for outcomes 1 to 4?

Reply | Quote

I think introducing the two groups G1 and G2 is artificial – in reality, the assignment of couples is done within the entire group of players.

Reply | Quote

I don’t think it matters. You can think if them as winners/losers or as the “home Team” and the “away team”. The numbers come out the same…

Steve

Reply | Quote

Yes, your reply above explains it nicely. Thanks!

Reply | Quote

(Edited by sdckapr on 08-Oct-05 11:53. Added PS)

I got the numbers assuming group 1 were the winners of Round 1 and Group2 were the losers. But if you are thinking of Group 1 as 1 side and Group 2 as their respective opponents in Round, it still comes out the same.

Player A:
Group 1 50%

So if Player A is in Group 1, Player B does not have a 50/50 chance of the 2 groups:
Group 1 has only 31 positions left so the prob is 31/63 and 32/63 in group2

If player B is in Group 2, then A has a 31/63 prob of Group 2 and 32/63 to be in Group 1

Thus:
1) A in 1, B in 1 is 50% * 31/63 = 31/126 = 24.6%
2) A in 1, B in 2 is 50% * 32/63 = 32/126 = 25.4%
3) A in 2, B in 1 is 50% * 32/63 = 32/126 = 25.4%
1) A in 2, B in 2 is 50% * 31/63 = 31/126 = 24.6%

The 2 results are not independent.

Now taking your logic
“The probability that A will meet B in round 1 under 1) and 4) above is zero. The probability that A will meet B in round 1 under 2) and 3) above is ” NOT 1/32 it equals 32/63. “Thus the total probability that A will meet B in round 1 is” 32/63/32 = 1/63.

Steve

PS note that the prob of EIther one in Group 1 or Group 2 is 24.6 + 25.4 = 50% as expected…

Reply | Quote

Ah – thanks for those probabilities …

[indent]

---

1) A in 1, B in 1 is 50% * 31/63 = 31/126 = 24.6%
2) A in 1, B in 2 is 50% * 32/63 = 32/126 = 25.4%
3) A in 2, B in 1 is 50% * 32/63 = 32/126 = 25.4%
4) A in 2, B in 2 is 50% * 31/63 = 31/126 = 24.6%

---

[/indent]I’m going to stick with my comment … “The probability that A will meet B in round 1 under 1) and 4) above is zero. The probability that A will meet B in round 1 under 2) and 3) above is 1/32” but I probably should have added “give that you have already allocated A to a match.”

The way I typically look at these sorts of things is … There are two groups of 32 people. One person from the first group is placed in each of the 32 matches. So A is placed in match M. Now, the chance that B is also placed in match M – and hence meets A in round 1 – is 1/32.

So, the chance (overall) that A meets B in the first round is
= 31/126 * 0% + 32/126 * 1/32 + 32/126 * 1/32 + 31/126 * 0
= 0 + 1/126 + 1/126 + 0
= 2/126
= 1/63.

Which is a long way of saying that my answer is that post was WRONG because I had thought that the four outcomes all had a 25% probability and led me (incorrectly) to 1/64.

Reply | Quote

That seems to be a convoluted way to arrive at it , in my opinion.

Imagine you have 64 spots for people in Round 1. A will have 1 of the 63 opponents (he will not play against himself). So the chance of a particular person being his opponent is 1/63. There is no need to divide them into an artificial group (although as demonstrated, the logic is the same, as it should be)

Steve

Reply | Quote