Friday, August 31, 2007

Puzzle

Taken from an NSA blog:

A round-robin tournament is being held; in every match, each player has a 50% chance of winning.

a. (Warmup). If there are three players, what's the probability that each ends up with a 1-1 record?
b. (Not too bad). If there are five players, what's the probability that each ends up with a 2-2 record?
c. (Harder). If there are seven players, what's the probability that each ends up with a 3-3 record? Can you come up with a general formula for n players (n odd)?

Anyone?Andy?

5 comments:

jkqxz said...

I have figured out the 3 players case!

What I did was to draw a graph with players as nodes and join the nodes with directed links to indicate who is the winner.

For each player to have a 1-1 record, each node must have one outgoing link and one incoming link.

By trial and error, I found out that there are two cases:

Case 1:
A --> B --> C --> A
A wins B, B wins C and C wins A

Case 2:
A <-- B <-- C <-- A
A lose to B, B lose to C and C lose to A

So, probability for 1-1 record for 3 players = 2 / 2^3 = 0.25

Haven't quite figured out how to extend this idea to 5 or more players yet though. Will think about it a bit more during the weekend.

jkqxz said...

Here is my attempt at the quiz.

Let f(n) be the number of ways for each player in a n-player tournament to have (n-1)/2 wins and (n-1)/2 losses, p(n) be the probability and the players be denoted as a0, a1, ... an-1.

We can see easily that f(3) = 2,
p(3) = 2 / 2^(3C2) = 0.25

For n = 5, a0 has 4C2 ways of winning two games and losing two games.

I then group the players that lose to a0 together as group X and the players that win a0 together as group Y and assume that it is possible to have a one-to-one mapping between elements in group X and group Y. Each one-to-one mapping denotes a win for an element in group X. There are 2! ways to do this mapping.

After discounting the games with a0 and the one-to-one mapping, we are left with 3 players that has a 1-1 record with each other.

So, f(5) = 4C2 x 2! x f(3) = 24
p(5) = 24 / 2^(5C2) = 3/128

For n = 7, I use the same logic as above and find that

f(7) = 6C3 x 3! x f(5) = 20x6x24 = 2880
p(7) = 2880 / 2^(7C2) = 45/2^15

In general,
f(n) = (n-1)C((n-1)/2) x ((n-1)/2)! x f(n-2)
= ((n-1)! x (n-3)! x ... x 2)/(((n-1)/2)! x ((n-3)/2)! x .. x 1)

p(n) = f(n) / 2^(nC2)

aaron said...

Ok here I go.

(i)Let X = number of wins by a player

X~b(2,1/2)

P(X=1) = 2C1*(1/2)^2 = 1/2
which is the probability of one player to win one game out of two

Since there are three players and there are two ways for each player to be paired up against:
2!*(1/2)^3 = 1/4

(ii) Using the same concept I got
4!*(4C2*(1/2)^4)^5

(iii) 6!*(6C3*(1/2)^6)^7

Generally,
(n-1)!*((n-1)C((n-1)/2)*(1/2)^n-1)^n

jkqxz said...

Realised that my logic for the general n-player case is not correct as the n-2 players left already have some matches played between some of them and it is not true that there are f(n-2) ways to link them all up.

I have tried exhaustively listing down all the possible combinations for the 5 players case and I found that there are 24 cases, so the 5 players case just happened to be correct.

Hubert, let us know what is the standard answer once you have it. Thanks!

jkqxz said...

Found a link at http://www.math.niu.edu/~rusin/known-math/97/tournaments that seems to suggest that no general solution has been found but it is published 10 years ago. Wonder if any progress has been made since then.