The Extremal Principle

In one sentence

A crowd of objects, conditions that treat everyone equally, and you do not know who to look at first: then look for the most special one, the largest, the smallest, the one at the very edge. It has already “hit the end”: the others still have room to move, but it does not. Apply the conditions to it, and a contradiction often pops out.

Before you use it, check just one thing: this “most” one really exists.

Predict first

Six numbers stand in a circle, and each one equals the average of its two neighbors. Can the six numbers be not all equal?

Yes, you can tune themNo, they must all be equal

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

Example: every number is the average of its neighbors

Step 1 / 4

Everyone is equal: where to start?
Six numbers, all with exactly the same condition. Trying them one by one never ends.
Watch the largest
The only way out
Pass it round the circle

Stop 1 · The player who won the most games (Vol. 7)

In a round-robin tournament, every two players play one game, and there are no draws. We want to prove a classic fact:

There is always a player $A$ such that for every other player $B$ : either $A$ beat $B$ , or $A$ beat someone who beat $B$ .

With so many players, who is $A$ ? Let the extremal principle choose.

Example: finding player A

Step 1 / 4

Pick the one with the most wins
There are finitely many players, so “the player with the most wins” must exist (if several tie, pick any of them). Let that player be $A$ .

$A : most wins$
Suppose A fails
Count B’s wins
Contradiction

Stop 2 · The smallest solution can get smaller (Vol. 6)

A fraction in lowest terms has a numerator and denominator with no common factor. Turn this idea around and you get the extremal principle of number theory: assume there is a solution, take the smallest, and build an even smaller one.

Predict first

Are there positive integers $p, q$ with $p^{2} = 2 q^{2}$ ?

Yes, but they are very largeNo

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

Example: p² = 2q² has no positive integer solutions

Step 1 / 4

Assume a solution; take the smallest
If there is a solution, take the pair $(p, q)$ with the smallest $q$ among all solutions. $q$ is a positive integer, and any collection of positive integers has a smallest member, so this is possible.

$p^{2} = 2 q^{2}, q smallest$
p is even
Substitute back
It is smaller than the smallest

Stop 3 · The triangle of largest area (Vol. 4)

A well-known classic:

There are finitely many points in the plane, and every triangle formed by three of them has area at most $1$ . Prove that all the points can be covered by one triangle of area at most $4$ .

Example: covering every point with one big triangle

Step 1 / 4

So many triangles: which one to watch?
$6$ points make $20$ triangles, all of different sizes.
Watch the one with the largest area
Draw parallels through the three vertices
Why it covers everything

Practice

Exercise 1Basic

$8$ numbers stand in a circle, and each one equals the average of its two neighbors. One of them is $5$ . What is the sum of the $8$ numbers?

Exercise 2Advanced

$10$ players play a round-robin tournament: every two players play one game, and there are no draws. Whatever the results, the player who wins the most games wins at least how many games?

Exercise 3Challenge

Prove that the equation $x^{2} + y^{2} = 3 z^{2}$ 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 a “smallest” that does not exist

Among all positive fractions, take the smallest one and call it

q

…

What went wrong? Think first, then open

Diagnosis There is no smallest positive fraction: however small $q$ is, $\frac{q}{2}$ is a positive fraction too, and smaller. Reasoning about something that does not exist proves nothing.

First ask: “does a smallest one exist?”. Among finitely many numbers there is always a largest and a smallest; any collection of positive integers (even infinitely many) has a smallest. In any other situation, prove it exists first.

“Make sure the extreme one exists before you take it”

Exhibit

Assuming there is only one largest

Let

a

be the largest number on the circle. Then both its neighbors are smaller than it, so…

What went wrong? Think first, then open

Diagnosis Several numbers can tie for largest. The neighbors are only not larger than it, and they may well be equal to it. In fact, the conclusion of the circle problem is exactly that “they are all equal”.

Write “

\leq

”, not “

<

”: the neighbors are

\leq a

, so their average is

\leq a

, and equality holds only if both neighbors equal

a

“The largest need not be unique”

In one sentence

Stop 1 · The player who won the most games (Vol. 7)

Stop 2 · The smallest solution can get smaller (Vol. 6)

Stop 3 · The triangle of largest area (Vol. 4)

Practice

Mistake Museum · Exhibits from this stop

Stops on this line