"In the parliament of Sikinia, each member has at most three enemies. Prove that the house can be separated into two houses, so that each member has at most one enemyin his own house."
This is an example question from "Problem Solving Strategies" by Arthur Engel .
The solution goes as follows:
Initially, separate the members into two houses in any manner. Let H be the total sum of all enemies each member has in his own house. Now suppose there is a person A who has at least two enemies in his own house. Then he has at most one enemy in the other house, so if A switches houses, H will decrease. Since H is necessarily a non-negative integer, it cannot decrease forever, so at some point this process ends. This means we cannot any longer find a person who has at least two enemies in their own house, which is precisely the assignment requested.
What I am not able to understand is that the solution accounts for only one house.
What if the person A who was shifted from one house to the other was enemy with some other person in the other house?
Best Answer
This solution implicitly assumes that the "enemy" relation is symmetric, i.e. if $B$ is $A$'s enemy, then $A$ is also $B$'s enemy.
Now suppose $A$'s enemies are $B, C,D,$ and out of these three, $B,C$ are in $A$'s house initially. So the algorithm will pick $A$ and move $A$ to the other house. Thus, $B$ has one fewer same-house enemy ($A$), $C$ has one fewer same-house enemy ($A$), $A$ has one fewer same-house enemy (losing $B,C$ but adding $D$), and $D$ has one more same-house enemy ($A$). The net effect is $H$ has changed by $(-1) + (-1) + (-1) + 1 = -2$, i.e. decreased by $2$.
If the enemy relation is not symmetric, then the invariant doesn't hold: e.g. while $A$ lost $B,C$ and gained $D$ as same-house enemies, if there is no symmetry then there might exist $S,T,U,V,W,X,Y,Z$ etc in the new house all who think $A$ is their enemy (even though $A$ doesn't think they are $A$'s enemy). So in this case $H$ might increase, breaking the argument.