[I got this puzzle from Jason Koenig.] 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? [Hint: As Radu Grigore pointed out to me, solving the Planar configuration of straight connecting lines puzzle may provide a hint to solving this puzzle.]

July 2011