# Enemy/Defender Probability

• Oct 29th 2010, 01:53 PM
Henderson
Enemy/Defender Probability
In a game of n people, each person is asked to select two other players. No player knows whether or not they've been selected. What is the probability that at least one person is not selected by anyone?

What we've got so far:

For n=3 players, it is impossible for anyone to be left out.

For n=4 players, the probability that one player is left out is $\frac{12}{81} = \frac{4}{27}$.

For n=5 players, the probability that one player is left out is $\frac{2340}{7776} = \frac{65}{216}$.

For n=5 players, the probability that two players are left out is $\frac{90}{7776} = \frac{5}{432}$.

For n=5 players, the overall probability that someone is left out is $\frac{2430}{7776} = \frac{5}{16}$.

For n=6 players, the probability that one player is left out is $\frac{380700}{1000000} = \frac{3807}{10000}$.

For n=6 players, the probability that two players are left out is $\frac{42120}{1000000} = \frac{1053}{25000}$.

For n=6 players, the probability that three players are left out is $\frac{540}{1000000} = \frac{27}{50000}$.

For n=6 players, the overall probability that someone is left out is $\frac{423360}{1000000} = \frac{1323}{3125}$.

For n players, the denominator will be $\binom{n-1}{2}^n$.

Any thoughts on how to generalize this, or any similar problems we could relate this back to? Thanks!
• Oct 29th 2010, 03:38 PM
brennan
I you are in a group of 'x' people - there are x-1 people you can choose your pair from.

So you can choose $\frac{(x-1)!}{(x-3)!2!}$ possible pairs.

For 4 people we have - $\frac{(4-1)!}{(4-3)!2!} = \frac{3!}{1!2!} = 3$ possible pairs.

Because there are x people in the group you can do it x times, so we have: $\frac{x(x-1)!}{(x-3)!2!}$ possible pairs:

For 4 people we have - 3 x 4 = 12 pairs. (the denominator)

Now if you where not there you would not be chosen - so there are now x-1 people playing - substitute x-1 in to the previous formula to get the number of pairs not including 1 person.

We get:
Numerator: $\frac{(x-1)(x-2)!}{(x-3)!2!}$
Denominator: $\frac{x(x-1)!}{(x-3)!2!}$
If you can simplify this factorial stuff pls do.

This gives probabilites of not being chosen as:

4 people: 3/12
5 people: 12/30
6 people: 30/60
7 people: 60/105

Now to generalise:

n people - choosing m (eg 5 people chosing 2 people)
We get:
Numerator: $\frac{(n-1)(n-2)!}{(n-m-1)!m!}$
Denominator: $\frac{n(n-1)!}{(n-m-1)!m!}$

i thonk there is an error here but im tired - i look again soon.
• Oct 31st 2010, 01:53 PM
awkward
Try PIE
Hint: Use the Principle of Inclusion/Exclusion to find the complementary probability, i.e. the probability that no-one is left out.

Consider the set of all possible selections, where we define a selection as the two pals chosen by each player. (Maybe it's easier, or at least less ambiguous, to visualize a selection as an n by n matrix of ones and zeros, where the diagonal elements are zero and each row contains exactly two ones.) Each player can choose any two of the remaining n-1 players, so he has $\binom{n-1}{2}$ possible choices of pairs. So altogether there are $N = \binom{n-1}{2}^n$ possible selections, each of which we assume is equally likely.

We would like to find the number of selections where no one is left out. To that end, let $E_i$ be the set of selections which omit player i. We want to count the selections which are in none of the $E_i$s. (Sounds like a job for PIE.) If you can find this number (call it $N_0$), then the probability that no one is left out is
$\frac{N_0}{N}$,
and the probability that at least one person is left out is
$1- \frac{N_0}{N}$.