Results 1 to 7 of 7

Thread: proof: pair up people from different sets; no pair from same set

  1. #1
    Newbie
    Joined
    Nov 2015
    From
    netherlands
    Posts
    4

    proof: pair up people from different sets; no pair from same set

    imagine you have people from different groups and you would like to pair them up so that no pair is constituted by people of the same group. i've spent a couple of minutes simulating different possibilities and have come to the conclusion that it is always possible given that no set (group) has more than $\displaystyle n/2$ elements (people) in it.

    but i am looking for a mathematical proof or some reference of what this problem is called. i have a feeling it is a very general set theory concept and i'm overcomplifying it.
    thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,405
    Thanks
    3296
    Awards
    1

    Re: proof: pair up people from different sets; no pair from same set

    Quote Originally Posted by foerno View Post
    imagine you have people from different groups and you would like to pair them up so that no pair is constituted by people of the same group. i've spent a couple of minutes simulating different possibilities and have come to the conclusion that it is always possible given that no set (group) has more than $\displaystyle n/2$ elements (people) in it.
    but i am looking for a mathematical proof or some reference of what this problem is called. i have a feeling it is a very general set theory concept and i'm oversimplifying it.
    Actually, one can do this if in each set has the same number of members. This assumes two groups and everyone is assigned to a couple with someone from the other group. If this is an incorrect reading of the question please correct me. If there are more than two groups please explain exactly the setup.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2015
    From
    netherlands
    Posts
    4

    Re: proof: pair up people from different sets; no pair from same set

    Quote Originally Posted by Plato View Post
    Actually, one can do this if in each set has the same number of members. This assumes two groups and everyone is assigned to a couple with someone from the other group. If this is an incorrect reading of the question please correct me. If there are more than two groups please explain exactly the setup.
    this is correct except the number of groups is variable (let's say $\displaystyle m$). the number of members of each group is also variable - $\displaystyle n(i)$. for $\displaystyle m=2$ the problem is, of course, trivial.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,405
    Thanks
    3296
    Awards
    1

    Re: proof: pair up people from different sets; no pair from same set

    Quote Originally Posted by foerno View Post
    this is correct except the number of groups is variable (let's say $\displaystyle m$). the number of members of each group is also variable - $\displaystyle n(i)$. for $\displaystyle m=2$ the problem is, of course, trivial.
    If each of $A~\&~B$ is a finite set and $|A|=|B|=m$ (number in the sets) then all you must do is construct a injection from $A\to B$.
    An injection is a one-to-one function, a unique pairing. There are $m!$ (factorial) such mappings.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2015
    From
    netherlands
    Posts
    4

    Re: proof: pair up people from different sets; no pair from same set

    Quote Originally Posted by Plato View Post
    If each of $A~\&~B$ is a finite set and $|A|=|B|=m$ (number in the sets) then all you must do is construct a injection from $A\to B$.
    An injection is a one-to-one function, a unique pairing. There are $m!$ (factorial) such mappings.
    no, no, you misunderstood. $m$ is the number of sets. but |A1|, |A2|, ... , |Am| can all be different. the point is, no matter how many sets or how many items, the point is to show the requirements necessary in order to create non-homogenous pairs (i.e. each item is paired with an item from a different set). i think the only requirement is that $n$ is even, and $\forall i : 1 \leq i \leq m, |A$i$| \leq \frac{n}{2}$ where $n$ is the total number of items and $m$ is the total number of sets. but i'm looking for a mathematical proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2015
    From
    netherlands
    Posts
    4

    Re: proof: pair up people from different sets; no pair from same set

    anyone else?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,405
    Thanks
    3296
    Awards
    1

    Re: proof: pair up people from different sets; no pair from same set

    Quote Originally Posted by foerno View Post
    anyone else?
    Can anyone else understand the problem? I doubt it! It seems to be terribly confusing.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Closest pair of sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 12th 2010, 11:14 AM
  2. Number of possible pair sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Aug 4th 2010, 11:27 PM
  3. Pair
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 1st 2010, 08:02 AM
  4. Voronoi tesselation for a pair of convex sets
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Jan 24th 2010, 11:28 AM

Search Tags


/mathhelpforum @mathhelpforum