The Affirmative Action Problem

The Affirmative Action problem has been posed by Donald Newman [Zeitz, p. 23]:

The applet below starts with a configuration of 20 nodes. The nodes (and edges) can be removed one at a time (Remove last) or all at once (Clear). You can create new nodes by starting to drag anywhere in the applet. Clicking inside a node changes its color.

The proof is due to Jim Propp.

Call an edge balanced if it joins two differently colored nodes. The proof elaborates on the one-liner: Maximize the number of balanced edges!

Since the number of nodes is finite, so is the number of possible color assignments. Hence, there are colorings with the maximal number of balanced edges. Any such coloring is bound to be integrated.

To see why this is so, consider a non integrated node. Without loss of generality we may assume it colored white. The fact the the node is not integrated can be rephrased in terms of the incident edges. The edges joining the node to the black neighbors are balanced, those joining it to the white neighbors are not. We conclude, that, among the edges incident to the non integrated node, there are fewer balanced than unbalanced edges. Changing the color of such a node, makes its incident balanced edges unbalanced, and vice versa. The operation therefore increases the total number of balanced edges.

Now, we see that the existence of a non integrated node in a coloring with a maximal number of balanced edges leads to a contradiction. Thus we conclude that, in such colorings, all nodes are necessarily integrated.

References

1. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999

Copyright © 1996-2008 Alexander Bogomolny