Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By romsek

Thread: No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

  1. #1
    Newbie
    Joined
    Dec 2016
    From
    Aberdeen, Scotland
    Posts
    6
    Thanks
    1

    No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

    There are 6 pairs (12 people) and they must be divided into 3 teams. All teams must have 1 or more occupants. Both people from a pair must not be in the same team.

    I already answered a similar question, the only difference was that there were two teams instead of three. If x is the number of pairs, I found the no. of ways to divide the pairs into 2 teams such that no pairs are in the same team, f(x), to be equal to the sum of (x-1) choose n from n=0 and n=(x-1). Another way of writing f(x) is f(x)=2^(x-1).

    Please correct me if I made a mistake, because chances are I did! I'm new to combinatorics and don't know a whole lot, but I really need an answer to this question
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,691
    Thanks
    2394

    Re: No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

    must the teams be of equal size?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2016
    From
    Aberdeen, Scotland
    Posts
    6
    Thanks
    1

    Re: No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

    No!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,691
    Thanks
    2394

    Re: No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

    maybe you've found some incredible shortcut but I'm seeing the problem as fairly complex.

    First off I'll assume that the teams do not have to be the same size. You didn't say they had to be.

    Clearly teams are of size 2-6, given that a pair cannot be on a team together and there are only 6 pairs.

    Also clearly the number of team members of the 3 teams must sum to 12.

    Given this there are a few combinations of team sizes that are valid

    $\left(
    \begin{array}{ccc}
    2 & 4 & 6 \\
    2 & 5 & 5 \\
    3 & 3 & 6 \\
    3 & 4 & 5 \\
    4 & 4 & 4 \\
    \end{array}
    \right)$

    Let's look at each of these.

    $(2,4,6)$ - a team of 6 must use one member of each pair.

    There are $2^6=64$ ways of selecting the 6 member team.

    We don't have to worry about pairs overlapping when choosing the 4 member team so there are ${_6C}_4 = 15$ ways of selecting this.

    Thus there are $N_{(2,4,6)} = 64\cdot 15=960$ ways of selecting this arrangement

    $(2,5,5)$ - When selecting the first 5 person team there are ${_6C}_5=6$ ways to select pairs and 2 ways to select a member from each pair so there are

    $6 \cdot 2^5 = 192$ possible combinations for the 5 person team.

    This leaves 5 pairs with 1 member, and 1 pair with 2 remaining.

    When selecting the 2nd 5 member team one has to include the pair with two remaining. Both pair members cannot be left for the final team.

    Thus we select that pair, and there are 2 ways of selecting that pair, then we have ${_5C}_4 = 5$ ways of choosing the other 4 members. So there are $2\cdot 5 = 10$ ways of selecting the 2nd 5 member team. The 2 member team is then fixed.

    Thus there is a total of $N_{(2,5,5)}=192 \cdot 10 =1920$ valid combinations of this arrangement

    $(3,3,6)$ - Again there are $2^6$ ways to select the 6 member team. Then there are ${_6C}_3 = 20$ ways to select the 3 member team

    so there are $N_{(3,3,6)}=64\cdot 20 = 1280$

    $(3,4,5)$ - As before there are $192$ ways to select the 5 member team.

    We must select the unused pair when selecting the 4 member team and can do that in 2 ways. Then there are ${_5C}_3 = 10$ ways to select the rest so there are

    $N_{(3,4,5)}=192 \cdot 2 \cdot 10 = 3840$ ways of selecting this arrangement

    $(4,4,4)$- there are ${_6C}_4 = 15$ ways to select 4 pairs and then 2 ways per pair to select members so there are

    $15\cdot 2^4 = 240$ ways to choose the first team

    Then two pairs are left which must be used for the 2nd team. There are 4 ways of selecting these 2 members and then ${_4C}_2=6$ ways to select the remaining 2 members. Thus there are $N_{(4,4,4)} = 240 \cdot 4 \cdot 6 = 5760$ valid combinations for this arrangement.


    Summing all these up we get

    $960 + 1920 +1280 + 3840+ 5760= 13760$ valid arrangements
    Thanks from phinbar
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Dec 2016
    From
    Aberdeen, Scotland
    Posts
    6
    Thanks
    1

    Re: No. of ways to divide 6 pairs into 3 teams so that no pairs are in the same team

    Wow, that is incredibly helpful. For some reason i was trying to find a general formula to answer the question for any number of pairs, I'm sure you can imagine how far I got trying that...
    Thanks
    Last edited by phinbar; Dec 1st 2016 at 12:25 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Factor pairs
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Oct 17th 2012, 06:39 PM
  2. Pairs in (A_n)^2
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 9th 2012, 12:56 AM
  3. Replies: 0
    Last Post: Apr 4th 2012, 09:12 AM
  4. distinct pairs
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 18th 2010, 03:51 AM
  5. Pairs of (x,y)
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: May 28th 2007, 07:11 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum