In a parliament there are 100 people, and some of these people are enemies with each other. Show that you can split the people in 2 groups, so that each person has at least as many enemies in the opposite group than 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 in 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.