The Extremal Principle: Choose the Smallest or Largest

1. All positive real numbers
2. The reciprocals of all positive integers
3. A nonempty finite set of positive real numbers
4. All integers

A smallest member must actually belong to the collection. A lower bound alone is not enough.

A nonempty finite list can be put in increasing order. Think about why the other collections keep offering a smaller member.

A nonempty finite set of positive real numbers

A nonempty finite set can be listed in increasing order; its first member is a smallest one. There is no smallest positive real number, because half of any proposed one is smaller and still positive. Among reciprocals of positive integers, $\frac{1}{n+1}$ is smaller than $\frac{1}{n}$. Among all integers, $n-1$ is smaller than n. Only the finite-set choice guarantees an attained minimum.

Watch out: Being bounded below does not mean that a smallest member exists: the reciprocals approach 0 but never include it.

1. 1 belongs to S
2. 2 belongs to S
3. Every member of S is even
4. S contains at least three numbers

Choose the smallest member of S, rather than starting with an arbitrary member.

If that smallest member were greater than 1, what would the rule put in S?

1 belongs to S

Let m be the smallest member; it exists because S is nonempty and finite. If m were greater than 1, the rule would put $\frac m2$ in S. This would be a positive number smaller than m, contradicting its choice. Therefore $m=1$. The set containing only 1 satisfies the condition, so 2, evenness of every member and a size of at least three are not forced.

Watch out: The rule itself guarantees that the halved value is a member when it applies. Do not assume in advance that every starting integer could occur in such a set.

1. 4
2. 5
3. 6
4. 9

Choose a position with the largest value M. Its neighbours are both at most M.

At that position, M is at most the neighbour average, while the average is at most M. What forces equality?

6

Choose a largest value M, with neighbours u and v. We have $u\le M$ and $v\le M$, so $\frac{u+v}{2}\le M$. The condition also gives $M\le\frac{u+v}{2}$. Thus equality holds throughout. If either neighbour were smaller than M, their average would be smaller than M, so both neighbours equal M. Apply the same argument successively around the circle: every value is M. Since the total is 36, $6M=36$ and $M=6$. Six copies of 6 satisfy every condition.

Watch out: A largest value need not occur at only one position. Here the argument proves that it occurs at every position.

1. 3
2. 4
3. 5
4. It cannot be determined

Repeatedly subtract the smallest member from a larger member. Every positive difference stays in S.

Can a member leave a remainder of 1, 2, 3, 4 or 5 after repeated subtraction of 6? Then start subtracting from 24.

4

If a member were not divisible by 6, repeatedly subtracting 6 would eventually produce a member between 1 and 5. This contradicts the smallest member being 6. Thus every member is a multiple of 6. Since no member exceeds 24, only 6, 12, 18 and 24 are possible. All four are forced: $24-6=18$, $18-6=12$, and 6 is given. The set {6,12,18,24} satisfies the difference condition, so the answer is exactly 4.

Watch out: Showing that members must come from a short list is only half the argument. Show that every entry on that list is present.

1. Only 1
2. Only 2
3. Either 1 or 2
4. 0, 1 or 2

The globally closest pair guarantees at least one mutual pair. Can two mutual pairs share a point?

For constructions, place the points on a line. Try coordinates 0,1,3,7,15, and then 0,1,10,12,30.

Either 1 or 2

A globally closest pair points to each other, so there is at least one mutual pair. Two mutual pairs cannot share a point because each point has only one outgoing arrow. Five points therefore allow at most two disjoint mutual pairs. Both bounds occur. For points on a line at 0,1,3,7,15, the only mutual pair is 0 with 1: the other arrows are $3\to1$, $7\to3$ and $15\to7$. Their ten distances are 1,2,3,4,6,7,8,12,14,15, all different. For coordinates 0,1,10,12,30, the mutual pairs are 0 with 1 and 10 with 12; the point 30 points to 12. The distances are 1,2,9,10,11,12,18,20,29,30, again all different. Hence exactly 1 and 2 are the possible counts.

Watch out: An upper bound is not automatically attainable. The coordinate constructions check existence and the no-ties condition.

1. The walk must finish at 9
2. The walk stops at a cell with no larger side-neighbour, after at most eight moves
3. The walk always uses eight moves
4. The walk cannot stop at a corner

A strictly increasing walk cannot revisit a cell. Count the available cells.

A value can be larger than all its immediate neighbours without being the largest on the entire board.

The walk stops at a cell with no larger side-neighbour, after at most eight moves

Each move strictly increases the number, so no cell can be visited twice. There are nine cells, allowing at most eight moves after the starting cell. The rule says to stop precisely when no larger side-neighbour exists. This does not force a finish at 9. Consider rows (8,1,2), (3,4,5), (6,7,9). Starting at the top-left 8 gives no legal move: its side-neighbours are 1 and 3. The walk stops immediately at a corner and does not reach 9. This single example also disproves the other proposed guarantees.

Watch out: A local maximum is greatest among its neighbours; a global maximum is greatest on the whole board. Do not confuse them.

1. 10
2. 11
3. 12
4. 13

Call the numbers $a<b<c$. Which pair sum is smallest, and how can you write it using c and the total?

If c were at most 7, the two smaller distinct integers could be at most 6 and 5. Can their total reach 20?

12

Write the numbers in order as $a<b<c$. The smallest pair sum is $a+b=20-c$, so making that sum large means making the largest entry c small. If $c\le7$, then $b\le6$ and $a\le5$, giving $a+b+c\le18$, contrary to the total 20. Hence $c\ge8$ and $a+b\le12$. The triple 5,7,8 has total 20 and pair sums 12,13,15. Its smallest pair sum is 12, so the bound is attained.

Watch out: There are two extremes here: the smallest of the pair sums, and the largest entry c. Rewrite the objective before choosing what to control.

1. 11
2. 12
3. 13
4. 16

A cut with an odd number of points to its left must be crossed by at least one pair. Otherwise all those points would be paired among themselves.

Use cuts in the gaps from 0 to 3, from 5 to 9, and from 10 to 16. Then give a pairing attaining the resulting bound.

13

Place a cut inside the gap from 0 to 3. One point is to its left, so at least one pair must cross that whole gap, contributing at least 3 to the total cost. A cut between 5 and 9 has three points to its left, and a cut between 10 and 16 has five; each odd count again forces a crossing pair. These gaps have lengths 4 and 6. A pair distance is the sum of the consecutive gaps it spans. When all pair distances are added, each crossed gap is counted once for each crossing pair, so the three forced gaps give a lower bound of $3+4+6=13$. Pair 0 with 3, 5 with 9, and 10 with 16. The costs are 3,4,6, with total 13. Therefore 13 is the minimum.

Watch out: The same pair may cross several forced gaps. That causes no overcounting because those gaps are disjoint parts of its distance.

1. Only 1
2. 1 or 2
3. Every positive integer size
4. Only even sizes

If there are at least two members, choose the two smallest ones, not the smallest and largest.

Where does the average of the two smallest distinct members lie?

Only 1

Suppose S has at least two members. Let a be its smallest and b its second-smallest, so $a<b$. Their average satisfies $a<\frac{a+b}{2}<b$. The stated property would put this average in S, strictly between the two smallest members, which is impossible. Thus S has only one member. A singleton, for example {0}, does satisfy the condition because there is no pair of distinct members to test. Hence size 1 is both necessary and possible.

Watch out: Finiteness supplies a second-smallest member. The set of all rational numbers is closed under averages but has no first or second-smallest member.

Take d to be the smallest member. Repeated subtraction of d cannot produce a positive member below d.

Use the largest member to show that none of the intermediate positive multiples of d can be missing.

Choose the smallest member d. Take any member a. If $a>d$, subtract d; the result remains in S and is positive. Continue while the current value exceeds d. The values decrease by a positive integer, so this process eventually reaches a value r with $1\le r\le d$. Since r belongs to S and d is its minimum, $r=d$. We have therefore subtracted d a whole number of times to reach d, showing that a is a positive integer multiple of d.

Now let the largest member be kd. Repeated subtraction gives $(k-1)d$, $(k-2)d$, …, d, so every positive multiple of d up to kd belongs to S. No larger number belongs to S by maximality, and no nonmultiple belongs by the first paragraph. Thus S is exactly {d,2d,…,kd}. When $k=1$ the subtraction list is empty and the conclusion still holds.

Conversely, take that set and two distinct members id and jd, with $i>j$. Their positive difference is $(i-j)d$, where $1\le i-j\le k-1$. It is one of the listed members. For a singleton there are no two distinct members to choose, so the condition holds as well. This proves both directions.

Check your proof: Did you justify that a minimum and maximum exist? Did you explain why repeated subtraction stays in S and stops? Did you exclude nonmultiples, force every intermediate multiple, and verify the converse including a singleton?

Choose an arrangement with the smallest possible largest pair sum. If its smallest and largest entries are not paired together, look at the two pairs containing them.

Write those pairs as (a,x) and (b,y), where a is a smallest remaining value and b a largest. Replace them with (a,b) and (x,y). Compare both new sums with $b+y$.

There are only finitely many ways to pair finitely many labelled entries, and at least one pairing exists. Therefore a pairing with a smallest possible largest sum exists. Choose one and call that largest sum T.

Let a be a smallest entry and b a largest. If they are paired together already, retain that pair. Otherwise they lie in two distinct pairs (a,x) and (b,y). Replace those pairs with (a,b) and (x,y). The entries have not changed and each is still used once, so this replacement is legal. Since $a\le y$ and $x\le b$, we have $a+b\le b+y$ and $x+y\le b+y$. The old sum $b+y$ was at most T. Thus both new pair sums are at most T, and all unchanged pairs also remain at most T.

We have obtained a pairing no worse than the optimum, with the smallest and largest entries paired together. Keep that pair fixed. Apply the same exchange to a smallest and largest entry among those still unpaired, changing only their two current pairs. Their values obey the same comparisons, so the global bound T is never increased. Repeat until every pair is fixed; after n steps this is the pairing produced by the stated rule. Its largest sum is at most T. Since T was already the minimum over all pairings, the rule attains that minimum.

If only two entries remain, they are already paired and no exchange is needed. Equal values cause no problem because the proof uses non-strict comparisons and the entries are labelled. This theorem explains the construction used in Example 3, while that example’s lower bound gives its numerical optimum.

Check your proof: Did you justify an optimal pairing exists? Did you state the two old and two new pairs? Did you compare both new sums with a known old sum? Did you explain why earlier fixed pairs stay fixed and why the process finishes?