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.

For each person, compute his animosity level by subtracting the number of enemies from the opposite group from the number of enemies in his own group. Now put 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. However, this yields a contradiction.

+ latest posts

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

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View All Comments
Share via
Copy link