Upend Congress and pour its members onto Constitution Avenue. Each member has up to three enemies. Prove that it’s possible to pack the 535 members back into the House and Senate in such a way that none of them has more than one enemy in his chamber. (Enmity is always mutual — I am my enemy’s enemy — and the chambers need not retain their former sizes.)
|
SelectClick for Answer |
Fill the House and Senate arbitrarily, and then consider each member in turn. If he has two or more enemies in his current chamber, then move him to the opposite one, where he’ll have no more than one enemy. If we repeat this operation then eventually every member will have at most one enemy in his chamber.
Adapted from Svetoslav Savchev and Titu Andreescu, Mathematical Miniatures, 2003.
12/30/2011 UPDATE: Wait, in paraphrasing Savchev and Andreescu’s solution I oversimplified it. (Thanks, John.) Here’s their solution:
“Form two chambers in an arbitrary way and denote by e the total number of pairs of enemies who are members of the same chamber. If there is a parliamentarian A who has at least two enemies in his chamber, send him to the other one, where he may have no more than one enemy. So at least two pairs of enemies disappear, while no more than one new pair can be formed. It follows that e decreases at least by 1 after this operation. Repeating the same several times, we will arrive at a situation when e cannot be decreased by more (because it is a nonnegative integer). This means that each parliamentarian will have at most one enemy in his or her chamber.”
|
