Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a set of boys and girls. A person can be either homo-, hetero- or bisexual so that they want to be with members of their own gender, the other gender or are indifferent towards gender.

How can I create pairs of these people so that each person wants to be with their partner? Is it possible to easily check if a solution exists?

share|improve this question
    
This is a variant of Hall's marriage theorem en.wikipedia.org/wiki/Hall%27s_marriage_theorem You might start there. –  Ross Millikan Nov 4 '11 at 13:04
8  
@Ross I think the more conservative members here will object. It will ruin the sanctity of Hall's marriage theorem! –  Ragib Zaman Nov 4 '11 at 13:08
3  
@Ragib: I think the more progressive members here will object to the heteronormative restriction of access to this theorem. –  joriki Nov 4 '11 at 13:13
    
Hopefully everyone knows I'm just joking =). –  Ragib Zaman Nov 4 '11 at 13:15
7  
@vicvicvic: So, in your model, a heterosexual woman would be happy to marry any man? –  Phira Nov 4 '11 at 13:15
show 2 more comments

1 Answer 1

up vote 6 down vote accepted

1) If the total number is not even, it won't work.

2) If there is an odd number of male homosexuals but no male bisexual, it won't work.

3) If there is an odd number of female homosexuals but no female bisexual, it won't work.

If these problems don't occur, marry off all the homosexuals using possibly one bisexual in either gender.

The remaining even number of heterosexual and bisexual people may have an overhang of one gender. This difference $d$ is even.

4) If there are less than $d$ bisexuals in the more frequent remaining gender, it won't work.

If there are (at least) $d$ bisexuals in the more frequent remaining gender, then marry them off and finally form heterosexual marriages with the rest.

share|improve this answer
    
I initially misinterpreted "if there are d bisexuals" to mean "exactly d". Thanks for the answer, it works smashingly! –  vicvicvic Nov 6 '11 at 19:47
2  
In simple terms: There have to be enough bi's to take care of the homos and heteros that cannot be paired off. –  Christian Blatter Nov 6 '11 at 21:13
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.