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

• Nov 16th 2015, 01:16 PM
foerno
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!
• Nov 16th 2015, 01:48 PM
Plato
Re: proof: pair up people from different sets; no pair from same set
Quote:

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.
• Nov 16th 2015, 02:10 PM
foerno
Re: proof: pair up people from different sets; no pair from same set
Quote:

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.
• Nov 16th 2015, 02:36 PM
Plato
Re: proof: pair up people from different sets; no pair from same set
Quote:

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.
• Nov 16th 2015, 11:27 PM
foerno
Re: proof: pair up people from different sets; no pair from same set
Quote:

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.
• Nov 26th 2015, 09:24 AM
foerno
Re: proof: pair up people from different sets; no pair from same set
anyone else?
• Nov 26th 2015, 10:14 AM
Plato
Re: proof: pair up people from different sets; no pair from same set
Can anyone else understand the problem? I doubt it! It seems to be terribly confusing.