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

1. ## 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!

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

Originally Posted by foerno
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.

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

Originally Posted by Plato
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.

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

Originally Posted by foerno
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.

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

Originally Posted by Plato
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.

anyone else?

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

Originally Posted by foerno
anyone else?
Can anyone else understand the problem? I doubt it! It seems to be terribly confusing.