Extremal Principle

The extremal principle is a technique that is useful for solving certain mathematical problems, by studying examples with extreme properties. This offers a useful starting point from which we can understand the simplified problem.

Most often the object or example we look at will have the smallest or largest value, in some sense. Recognizing when to use the extreme principle is often quite challenging. Some clues that can indicate that it would be helpful to use the extreme principle are:

1. The values in a question are distinct.
2. The possible set of values is bounded, either combinatorially (e.g. must choose a subset of a certain size) or absolutely (e.g. all numbers must be positive).
3. You have a monovariant.

It is one of the most useful tools in a problem solver's repertoire, and can be used to solve a great variety of problems. It basically depends on the seemingly obvious, but useful fact that every non-empty finite ordered set has a smallest and a largest element.

The use of the extremal principle is best understood by working through examples and that's what we're going to do right now!

Let's start with a simple example where the statement is proved by stating the obvious:

\(n\) students are standing in a field such that the distance between each pair is distinct. Each student is holding a ball, and when the teacher blows a whistle, each student throws their ball to the nearest student. Prove that there is a pair of students that throw their balls to each other.

-------
Consider the smallest distance between any pair of students. Since this is the smallest distance, the closest student to each of these is the other, so these students throw their ball to each other. \(_\square\)

Note: It is certainly possible for other pairs of students to throw their balls to each other. By focusing on an extremal object, we were easily able to identify a scenario that must always work.

The interesting problem below effectively showcases the power of the extremal principle:

Say you have finitely many red and blue points on a plane with the following interesting property: every line segment that joins two points of the same color contains a point of another color. Prove that all the points lie on a single straight line.

---

If you take out a pen and paper and start drawing points with this property, you might start to feel that if the points were not on a single line, then there can't be finitely many of them. You are right. But how do we prove this rigorously?

By using the extremal principle of course!

If the points were not a single straight line, you could draw different triangles with the points as vertices. Take the smallest such triangle, i.e. the triangle with the least area.

At least two of the vertices of this triangle have the same color. So between them is a point of different color. Join this point with the third vertex and you end up with two triangles, each having less area than the 'triangle with the least area'.

A contradiction! So all the points have to lie on a single line. \(_\square\)

See how easy that was! That's what looking at the extreme cases can do sometimes.

How do we know that there will always be a triangle with the least area? Not all ordered sets have a least element. For example, consider the interval \((2, 3]\).

The reason why there existed a triangle with the least area is that we had finitely many triangles, which was due to the fact that there were finitely many points to begin with.

So that's another thing to look out for when you want to use the extremal principle: make sure the extreme cases can exist, before you claim they do.

\(2n\) points are chosen in the plane such that no \(3\) are collinear. \(n\) are coloured blue and \(n\) are coloured red. Prove that there is a way to join the \(n\) red points to the \(n\) blue points by \(n\) line segments, such that no two line segments cross.

---

Suppose we join the red points \(R\) to the blue points \(B\) in an arbitrary fashion. If this does not have the desired property, then we must have a segment \(S_1\) joining \(R_1\) to \(B_1\) and a segment \(S_2\) joining \(R_2\) to \(B_2\) such that these segments intersect. If we instead let \(S_1\) connect \(R_1\) to \(B_2\) and \(S_2\) connect \(R_1\) to \(B_2,\) then these segments will no longer intersect. However, it is possible that the new \(S_1\) and \(S_2\) now intersect some other segments.

We notice that our swapping move decreases the total length of the segments (draw a figure and convince yourself this is the case). So, let us consider the configuration of segments \(S_1, S_2, \ldots, S_n\) that has minimal total length. Notice that such a minimum must exist, since there is a finite number of ways to pair the segments. If there was a pair of crossed segments in this configuration, then we could uncross them and get a smaller sum of lengths, contradicting our choice. Thus, this configuration has no pair of crossed segments. \(_\square\)

For \(n > 1,\) the integers from 1 to \(n^2\) are placed in the cells of an \(n \times n\) chessboard. Show that there is a pair of horizontally, vertically, or diagonally adjacent cells whose values differ by at least \(n+1.\)

-------
Consider the cells labelled \(1\) and \(n^2.\) There exists a sequence of at most \(k \leq n\) cells such that \(1 = c_1, c_2, \ldots, c_k =n^2\) and cells \(c_i\) and \(c_{i+1}\) are adjacent, for \(1 \leq i \leq k-1.\) If each pair of adjacent cells had value that differed by at most \(n,\) then the difference between \(c_1\) and \(c_k\) is at most \(n(n-1) = n^2 - n.\) However, the actual difference between them is \(n^2 - 1 > n^2 -n\) when \(n \geq 2.\) Thus, some pair along this chain have difference at least \(n+1.\) \(_\square\)

Consider an infinite chessboard, the squares of which have been filled with positive integers. Each of these integers is the arithmetic mean of four of its neighbors (above, below, left, right). Show that all the integers are equal to each other.

---

Consider the smallest integer on this board. Let's call it \(k\). If \(k\) is the arithmetic mean of its neighbors \(a, b, c\) and \(d,\) then we have

\[a+b+c+d=4k.\]

Now since \(k\) is the smallest integer on the board, none of \(a, b, c, d\) can be greater than or less than \(k\). So they have to be equal to \(k\). In other words, \(a=b=c=d=k.\)

It follows from this that all the integers are equal. \(_\square\)

In this example, how did we know that a smallest integer existed? Unlike the first one, we didn't have finitely many integers to deal with.

This actually follows from the well-ordering principle which states that every non-empty subset of non-negative integers always has a least element.

Another example:

In the coordinate plane, prove that the vertices of a regular pentagon cannot all be lattice points.

---

Before we begin, remember that a lattice point is a point with integer coordinates.

Now some of you are probably thinking something along the lines of trigonometry. Before we go into some (very messy) calculation, let's stop and think for a while.

What if we had such a pentagon? What would happen?

You might argue that if we had one such pentagon, we can make infinitely many such pentagons (how?). But that doesn't help us.

Now among all these pentagons, take the one that has the least area. Consider the five vectors \(v_i=a_i \hat{i}+b_i \hat{j} \text{ for } i \in \{1, 2, 3, 4, 5\}\) that point from one vertex to the next.

Note that \((a_i)^2+(b_i)^2=k^2,\) where \(k\) is the length of the side of the regular polygon.

Since \(\displaystyle \sum_{i=1}^5 v_i=0\), we must have \(\displaystyle \sum_{i=1}^5 a_i=0\) and \(\displaystyle \sum_{i=1}^5 b_i=0\).

Square the last two equations to get \(\displaystyle \sum_{i=1}^5 (a_i)^2+\displaystyle \sum_{i=1}^5 (b_i)^2+2\displaystyle \sum_{1\leq i< j\leq 5} (a_ia_j +b_ib_j)=0\).

So we see that \( \displaystyle \sum_{i=1}^5 (a_i)^2+\displaystyle \sum_{i=1}^5 (b_i)^2\) has to be even.

\(\displaystyle \sum_{i=1}^5 (a_i)^2+\displaystyle \sum_{i=1}^5 (b_i)^2\) is equal to \(5k^2\). This means \(k^2\) needs to be even and that implies that \(a_i\) and \(b_i\) have the same parity.

If \(a_1\) and \(b_1\) are both odd, then \(k^2\) is not a multiple of a \(4\). This means all \(a_i\) and \(b_i\) are odd. But if that happens, \(\displaystyle \sum_{i=1}^5 a_i\) can't be equal to zero since you can't get an even number by adding \(5\) odd numbers.

If \(a_1\) and \(b_1\) are both even, then \(4\) divides \(k^2\). This means that all \(a_i\) and \(b_i\) are even. Now we can scale our polygon by \(\frac{1}{2}\) to get another regular pentagon with lattice points as vertices but with a smaller area. That's a contradiction.

So, there can't be such a pentagon. \(_\square\)

Note that this argument works for any regular \(n\)-gon, where \(n\) is odd.

1) Prove that a cube cannot be divided into a finite number of smaller cubes, each of different sizes. Also, show that a hypercube cannot be hypercubed.

2) A finite set of points in the plane has the property that the triangle formed by any \(3\) of them has area less than \(1\). Prove that there is a triangle of area \(4\) that contains all the points.

3) Every vertex of a graph \(G\) has degree \(3\). Prove that we can partition the vertices of \(G\) into \(2\) sets \(A\) and \(B\) such that each vertex in \(A\) has at least 2 neighbours in \(B\) and each vertex in \(B\) has at least \(2\) neighbors in \(A.\)

• Invariant Principle
• The Well-Ordering Principle
• Proof by Contradiction
• Fermat's Method of Infinite Descent