Results 1 to 3 of 3

Math Help - Enemy/Defender Probability

  1. #1
    Member Henderson's Avatar
    Joined
    Dec 2007
    Posts
    124
    Thanks
    2

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2010
    Posts
    23
    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.
    Last edited by brennan; October 29th 2010 at 04:04 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    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_is. (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}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: January 21st 2011, 11:47 AM
  2. Replies: 3
    Last Post: May 29th 2010, 07:29 AM
  3. Replies: 1
    Last Post: February 18th 2010, 01:54 AM
  4. Replies: 3
    Last Post: December 15th 2009, 06:30 AM
  5. Abstract Algebra is my enemy
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 2nd 2009, 02:48 AM

Search Tags


/mathhelpforum @mathhelpforum