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.

You are given an irreflexive symmetric (but not necessarily transitive) "enemies" relation on a set of people. In other words, if person A is an enemy of a person B, then B is also an enemy of A. How can you divide up the people into two houses in such a way that every person has at least as many enemies in the other house as in their own house?

share|improve this question
    
I think I don't understand the question clearly. Could you elaborate on the following? "How can you divide up the people into two houses in such a way that every person has at least as many enemies in the other house as in their own house?" –  Spark Nov 9 '13 at 7:25

1 Answer 1

up vote 2 down vote accepted

Divide the people up however you like. Then, if there is anyone with more enemies in their own house than the other house, make them switch houses. (If there are multiple candidates, pick any one you like.) Keep doing this until everyone has at least as many enemies in the other house as in their own. Because each switch (by construction) reduces the total number of pairs of enemies that share a house, the procedure must terminate.

This is known as the "Happynet" problem. While it is simple to find a solution, as just described, no polynomial-time algorithm for finding one is known. (The algorithm I described can take exponential time in the worst case.)

share|improve this answer

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.