The Extremal Principle

In one sentence

The extremal principle: among a collection of objects, take the one where some quantity is largest (or smallest), and apply the conditions of the problem to it. It has “hit the end”: other objects could still be bigger, but it cannot. So it is the easiest place to get a strong conclusion, or a contradiction.

Before you use it, check three facts: finitely many real numbers always have a largest and a smallest; every nonempty set of positive integers has a smallest element; infinitely many real numbers need not have a largest or a smallest.

Predict first

A $5$ -player round robin: every two players play once, and there are no draws. Must the player with the most wins, against every other player, “either have beaten them directly, or have beaten someone who beat them”?

Yes, alwaysNot necessarily

Choose an answer first; then you can see the result.

Example: in a round robin, the player with the most wins beats everyone “directly or through one player”

Step 1 / 4

Take the extreme one
Let $K$ be the player with the most wins. $K$ beat $m$ players; call that set $W$ .

$∣ W ∣ = m is largest$
Suppose not
Count the wins of v
Contradiction

Stop 1 · Well-Ordering and Infinite Descent (Vol. 5)

Take the “smallest” positive integer solution, then build an even smaller one from it: infinite descent.

Example: the equation x² + y² = 3z² has no positive integer solutions

Step 1 / 4

Take the smallest solution
Suppose there is a positive integer solution. Every nonempty set of positive integers has a smallest element, so we can take the solution $(x, y, z)$ with the smallest $z$ .

$z smallest$
Look mod 3
Substitute back
A smaller solution

Stop 2 · Extrema with AM–GM (Vol. 6)

“How large can the smallest of several expressions be?” Call that minimum $m$ . It is at most each of the expressions; then multiply or add those inequalities to get rid of the variables.

Example: x, y > 0 and m = min{x, y/(x² + y²)}. Find the maximum of m

Step 1 / 4

m is at most each one
$m$ is the smaller of the two, so it is at most both of them.

$m \leq x, m \leq \frac{y}{x ^{2} + y ^{2}}$
Use AM–GM on the denominator
Multiply to remove x
Equality

Stop 3 · Extremum Problems in Analytic Geometry (Vol. 7)

Finitely many points make only finitely many triangles, so one with the largest area must exist. It is the “skeleton” of the whole picture.

Example: finitely many points in the plane, not all collinear; every triangle formed by three of them has area at most 1. Prove that all the points lie in some triangle of area at most 4

Step 1 / 4

Take the triangle of largest area
Among all triangles with vertices at these points, take the one of largest area, $△ A B C$ , with area $S \leq 1$ .

$S_{△ A B C} largest$
Build the big triangle
No point escapes
Contradiction

Practice

Exercise 1Basic

$5$ players play a single round robin (every two play once, no draws). What is the smallest number of games the player with the most wins can have won?

Exercise 2Advanced

$x, y > 0$ and $m = min {x, \frac{1}{y}, y + \frac{1}{x}}$ . The maximum of $m$ is $k$ . Find $k$ .

Exercise 3Advanced

There are finitely many points in the plane (at least two). Prove that they cannot all be midpoints of segments joining two other points of the set.

Exercise 4Challenge

Prove that the equation $x^{3} + 2 y^{3} = 4 z^{3}$ has no positive integer solutions.

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

Taking the “smallest solution” among positive reals

Suppose

x^{2} + y^{2} = 3 z^{2}

has a solution in positive reals. Take the one with the smallest

z

, and then …

What went wrong? Think first, then open

Diagnosis There is no smallest positive real: if $(x, y, z)$ is a solution, so is $(\frac{x}{2}, \frac{y}{2}, \frac{z}{2})$ . Besides, this equation really does have solutions in positive reals (for example $x = y = \frac{3}{2}$ , $z = 1$ ).

The well-ordering principle holds only for positive integers (or for finite sets). Infinite descent has to run among the positive integer solutions: take the positive integer solution with the smallest

z

“First make sure the “smallest” exists”

Exhibit

Most wins, so they must have beaten everyone

In a round robin, take the player

K

with the most wins. Since

K

has the most wins,

K

beat everyone.

What went wrong? Think first, then open

Diagnosis Most wins is not the same as winning every game. In a five-player round robin everyone can have exactly $2$ wins and $2$ losses, and then nobody is unbeaten. The extreme element is only “the most”; what it guarantees has to be proved.

What you can prove is this: for every other player,

K

either beat them directly or beat someone who beat them. The proof is by contradiction: if some

v

beat

K

and also beat everyone

K

beat, then

v

has more wins than

K

“The extreme element has an extreme property, but do not exaggerate it”

In one sentence

Stop 1 · Well-Ordering and Infinite Descent (Vol. 5)

Stop 2 · Extrema with AM–GM (Vol. 6)

Stop 3 · Extremum Problems in Analytic Geometry (Vol. 7)

Practice

Mistake Museum · Exhibits from this stop

Stops on this line