The Art and Craft of Problem Solving

74 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

different lines and other shapes. A good problem solver always tries to organize this

mass of stuff. A fundamental tactic is the extreme principle:

If possible, assume that the elements of your problem are "in order."

Focus on the "largest" and "smallest" elements , as they may be con­

strained in interesting ways.

This seems almost trite, yet it works wonders in some situations (for example, the

Affirmative Action problem on page 21). Here is a simple example.

Example 3.2.1 Let Band W be finite sets of black and white points, respectively, in

the plane, with the property that every line segment that joins two points of the same

color contains a point of the other color. Prove that both sets must lie on a single line

segment.

Solution: After experimenting, it seems that if the points do not all lie on a single

line, that there cannot be finitely many of them. It may be possible to prove this with

many complicated diagrams showing that "you can always draw a new point," but this

isn't easy. The extreme principle comes to the rescue: Assume that the points do not

all lie on a line. Then they form at least one triangle. Consider the triangle of smallest

area. Two of its vertices are the same color, so between them is a point of the other

color, but this forms a smaller triangle-a contradiction! _

Note how the extreme principle immediately cracked the problem. It was so easy

that it almost seemed like cheating. The structure of the argument used is a typi­

cal one: Work by contradiction; assume that whatever you wish to prove is not true.

Then look at the minimal (or maximal) element and develop an argument that cre­

ates a smaller (or larger) element, which is the desired contradiction. As long as a

set of real numbers is finite, it will have a minimum and a maximum element. For

infinite sets, there may be no extreme values (for example, consider the infinite set

{I, 2, 1/2,2^2 ,1/2^2 ,2^3 , 1/2^3 , ... }, which has neither a minimum nor a maximum el­

ement), but if the set consists of positive integers, we can use the Well-Ordering

Principle:

Every non-empty set of positive integers has a least element.

Here is another simple example. The tactic used is the extreme principle; the crux

move is a clever geometric construction.

Example 3.2.2 (Korea 1995) Consider finitely many points in the plane such that, if

we choose any three points A,B,C among them, the area of triangle ABC is always