Enemies in the Parliament

In a parliament, there are 100 people, and some of these people are enemies with each other. Show that you can split the people into 2 groups so that each person has at least as many enemies in the opposite group as he has in his own.

SOLUTION

For each split of the people into 2 groups, compute the animosity level of each person by subtracting the number of enemies in the opposite group from the number of enemies in his own group. Then, split the people into 2 groups so that the total animosity level of all of them is as little as possible. If there is a person, who has more enemies in his own group than the opposite one, then by transferring him to the other group, we will reduce the total animosity level of the people and will get a contradiction.

Unknown Author

We do not know where this puzzle originated from. If you have any information, please let us know via email.

Unknown Author

Puzzle Newsletter