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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.)