Technique Encyclopedia

Extremal Principle

What it is

The extremal principle means deliberately considering the maximum or minimum element of a set or configuration — the largest number, the shortest segment, the most-connected point. Extremes are often forced into a special relationship with the rest of the configuration that an arbitrary element wouldn't have, and that relationship can unlock a proof.

Signals that suggest using it

"Prove that there exists ..." in a finite set or configuration.
A problem about orderings, rankings, or configurations where singling out the biggest or smallest element seems natural.
Direct construction feels stuck, but the extreme case seems to force something.

When it's effective

Existence proofs in combinatorics — the extreme element's special status (nothing bigger, or nothing smaller) is often exactly the leverage needed to derive a contradiction or pin down a structure.

When it's not effective

If the extreme element in the configuration doesn't actually behave any differently from a typical element, singling it out adds no information and the technique doesn't help.

Simple example

Problem

A finite set S of positive integers has the property that whenever n is in S, so is every positive divisor of n. Prove 1 is in S.

Solution

Since S is a nonempty finite set of positive integers, it has a smallest element m. Because 1 divides m, and S contains every divisor of any element it contains, 1 must be in S.

AMC-style example

Problem

Let S be a finite set of positive integers with more than one element, where every divisor of any element of S is also in S. Prove S contains a prime.

Solution

S has more than one element, so it contains some element greater than 1. Let m be the smallest such element. If m were not prime, it would have a divisor d with 1; since d is also in S and d>1, this contradicts m being the smallest element of S greater than 1. So m must be prime.

Pigeonhole Principle Monovariants Testing Small Cases