3.5 Proofs by cases and by exhaustion

Proof by exhaustion is the least attractive proof method from an aesthetic perspective. An exhaustive proof consists of literally (and exhaustively) checking every element of the universe to see if the given statement is true for it. Usually, of course, this is impossible because the universe of discourse is infinite; but when the universe of discourse is finite, one certainly can’t argue the validity of an exhaustive proof.

In the last few decades, the introduction of powerful computational assistance for mathematicians has led to a funny situation. There is a growing list of important results that have been “proved” by exhaustion using a computer. Important examples of this phenomenon are the non-existence of a projective plane of order 10 (Lam (1991)) and the only known value of a Ramsey number for hypergraphs (Radziszowski (1996)).

Proof by cases is subtly different from exhaustive proof — for one thing a valid proof by cases can be used in an infinite universe. In a proof by cases, one has to divide the universe of discourse into a finite number of sets³¹ and then provide a separate proof for each of the cases. A great many statements about the integers can be proved using the division of integers into even and odd. Another set of cases that is used frequently is the finite number of possible remainders obtained when dividing by an integer. (Note that even and odd correspond to the remainders \(0\) and \(1\) obtained after division by \(2\).)

A very famous instance of proof by cases is the computer-assisted proof of the four-colour theorem. The four-colour theorem is a result known to map makers for quite some time that says that four colours are always sufficient to colour the nations on a map in such a way that countries sharing a boundary are always coloured differently. Figure 3.2 shows one instance of an arrangement of nations that requires at least four different colours. The theorem says that four colours are always enough. It should be noted that real cartographers usually reserve a fifth colour for oceans (and other water) and that it is possible to conceive of a map requiring five colours if one allows the nations to be non-contiguous. In 1977, Kenneth Appel and Wolfgang Haken proved the four-colour theorem by reducing the infinitude of possibilities to 1,936 separate cases and analyzing each of these with a computer.

The inelegance of a proof by cases is probably proportional to some power of the number of cases. But in any case, the proof by Appel and Haken is generally considered somewhat inelegant. Ever since the proof was announced, there has been an ongoing effort to reduce the number of cases (currently the record is 633 cases — still far too many to be checked through without a computer) or to find a proof that does not rely on cases. Wikipedia has a good introductory article on the four-colour theorem³².

Figure 3.2: The nations surrounding Luxembourg show that sometimes 4 colours are required in cartography.

Most exhaustive proofs of statements that aren’t trivial tend to either be (literally) too exhausting or to seem rather contrived. One example of a situation in which an exhaustive proof of some statement exists is when the statement is thought to be universally true but no general proof is known — yet the statement has been checked for a large number of cases. Goldbach’s conjecture is one such statement.

Christian Goldbach³³ was a mathematician born in Königsberg Prussia, who, curiously, did not make the conjecture³⁴ which bears his name. In a letter to Leonard Euler, Goldbach conjectured that every odd number greater than 5 could be expressed as the sum of three primes (nowadays this is known as the weak Goldbach conjecture).

Euler apparently liked the problem and replied to Goldbach stating what is now known as Goldbach’s conjecture: Every even number greater than 2 can be expressed as the sum of two primes. This statement has been lying around since 1742, and a great many of the world’s best mathematicians have made their attempts at proving it — to no avail! (Well, actually a lot of progress has been made but the result still hasn’t been proved.) It’s easy to verify the Goldbach conjecture for relatively small even numbers, so what has been done is/are proofs by exhaustion of Goldbach’s conjecture restricted to finite universes. As of this writing, the conjecture has been verified to be true of all even numbers less than \(2 \times 10^{17}\).

Whenever an exhaustive proof or a proof by cases exists for some statement, it is generally felt that a direct proof would be more esthetically pleasing. If you are in a situation that doesn’t admit such a direct proof, you should at least seek a proof by cases using the minimum possible number of cases. For example, consider the following theorem and proof.

Theorem 3.6 \(\forall n \in {\mathbb Z}\; n^2 \;\) is of the form \(4k\) or \(4k+1\) for some \(k \in {\mathbb Z}\).

Proof. We will consider the four cases determined by the four possible residues modulo 4.

1. If \(n \equiv 0 \pmod{4}\) then there is an integer \(m\) such that \(n = 4m\). It follows that \(n^2 = (4m)^2 = 16m^2\) is of the form \(4k\) where \(k\) is \(4m^2\).

2. If \(n \equiv 1 \pmod{4}\) then there is an integer \(m\) such that \(n = 4m+1\). It follows that \(n^2 = (4m+1)^2 = 16m^2 + 8m + 1\) is of the form \(4k+1\) where \(k\) is \(4m^2+2m\).

3. If \(n \equiv 2 \pmod{4}\) then there is an integer \(m\) such that \(n = 4m+2\). It follows that \(n^2 = (4m+2)^2 = 16m^2 + 16m + 4\) is of the form \(4k\) where \(k\) is \(4m^2+4m+1\).

4. If \(n \equiv 3 \pmod{4}\) then there is an integer \(m\) such that \(n = 4m+3\). It follows that \(n^2 = (4m+3)^2 = 16m^2 + 24m + 9\) is of the form \(4k+1\) where \(k\) is \(4m^2+6m+2\).

Since these four cases exhaust the possibilities and since the desired result holds in each case, our proof is complete.

 

While the proof just stated is certainly valid, the argument is inelegant since a smaller number of cases would suffice.

Exercise 3.8 The previous theorem can be proved using just two cases. Do so.

We’ll close this section by asking you to determine an exhaustive proof where the complexity of the argument is challenging but not too impossible.

Graph pebbling is an interesting concept originated by the famous combinatorialist Fan Chung. A “graph” (as the term is used here) is a collection of places or locations which are known as “nodes,” some of which are joined by paths or connections which are known as “edges.” Graphs have been studied by mathematicians for about 400 years, and many interesting problems can be put in this setting. Graph pebbling is a crude version of a broader problem in resource management — often a resource actually gets used in the process of transporting it. Think of the big tanker trucks that are used to transport gasoline. What do they run on? Well, actually they probably burn diesel — but the point is that in order to move the fuel around we have to consume some of it. Graph pebbling takes this to an extreme: in order to move one pebble we must consume one pebble.

Imagine that a bunch of pebbles are arbitrarily distributed on the nodes of a graph, and that we are allowed to do graph pebbling moves — we remove two pebbles from some node and place a single pebble on a node that is connected to it. See Figure 3.4.

Figure 3.3: In graph pebbling problems a collection of pebbles are distributed on the nodes of a graph. There is no significance to the particular graph that is shown here, or to the arrangement of pebbles — we are just giving an example.

Figure 3.4: A graph pebbling move takes two pebbles off of a node and puts one of them on an adjacent node (the other is discarded). Notice how node C, which formerly held 3 pebbles, now has only 1 and that a pebble is now present on node D where previously there was none.

For any particular graph, we can ask for its pebbling number, \(\rho\). This is the smallest number so that if \(\rho\) pebbles are distributed in any way whatsoever on the nodes of the graph, it will be possible to use pebbling moves so as to get a pebble to any node.

For example, consider the triangle graph — three nodes which are all mutually connected. The pebbling number of this graph is 3. If we start with one pebble on each node we are already done; if there is a node that has two pebbles on it, we can use a pebbling move to reach either of the other two nodes.

Exercise 3.9 There is a graph \(C_5\) which consists of 5 nodes connected in a circular fashion. Determine its pebbling number. Prove your answer exhaustively.

Hint: the pebbling number must be greater than 4 because if one pebble is placed on each of the four nodes, the configuration is unmovable (we need to have two pebbles on a node in order to be able to make a pebbling move at all) and so the 5th node can never be reached.

3.5.1 Exercises

1. Prove that if \(n\) is an odd number then \(n^4 \pmod{16} = 1\).

2. Prove that every prime number other than 2 and 3 has the form \(6q+1\) or \(6q+5\) for some integer \(q\). (Hint: this problem involves thinking about cases as well as contrapositives.)

3. Show that the sum of any three consecutive integers is divisible by 3.

4. There is a graph known as \(K_4\) that has \(4\) nodes and there is an edge between every pair of nodes. The pebbling number of \(K_4\) has to be at least \(4\) since it would be possible to put one pebble on each of \(3\) nodes and not be able to reach the remaining node using pebbling moves. Show that the pebbling number of \(K_4\) is actually \(4\).

5. Find the pebbling number of a graph whose nodes are the corners and whose edges are the, uhmm, edges of a cube.

6. A vampire number is a \(2n\) digit number \(v\) that factors as \(v=xy\) where \(x\) and \(y\) are \(n\) digit numbers and the digits of \(v\) are the union of the digits in \(x\) and \(y\) in some order. The numbers \(x\) and \(y\) are known as the “fangs” of \(v\). To eliminate trivial cases, pairs of trailing zeros are disallowed.

   1. Show that there are no 2-digit vampire numbers.

   2. Show that there are seven 4-digit vampire numbers.

7. Lagrange’s theorem on representation of integers as sums of squares says that every positive integer can be expressed as the sum of at most \(4\) squares. For example, \(79 = 7^2 + 5^2 + 2^2 + 1^2\). Show (exhaustively) that \(15\) can not be represented using fewer than \(4\) squares.

8. Show that there are exactly \(15\) numbers \(x\) in the range \(1 \leq x \leq 100\) that can’t be represented using fewer than \(4\) squares.

9. The trichotomy property of the real numbers simply states that every real number is either positive or negative or zero. Trichotomy can be used to prove many statements by looking at the three cases that it guarantees. Develop a proof (by cases) that the square of any real number is non-negative.

10. Consider the game called “binary determinant tic-tac-toe”³⁵ which is played by two players who alternately fill in the entries of a \(3 \times 3\) array. Player One goes first, placing 1’s in the array and player Zero goes second, placing 0’s. Player One’s goal is that the final array have determinant 1, and player Zero’s goal is that the determinant be 0. The determinant calculations are carried out mod 2.

    Show that player Zero can always win a game of binary determinant tic-tac-toe by the method of exhaustion.

References

Lam, C. W. H. 1991. “The Search for a Finite Projective Plane of Order 10.” Am. Math. Monthly 98 (4). Washington, DC, USA: Mathematical Association of America:305–18. https://doi.org/10.2307/2323798.

Radziszowski, Stanisław P. 1996. “Small Ramsey Numbers.” The Electronic Journal of Combinatorics [Electronic Only] DS01. Prof. André Kündgen, Deptartment of Mathematics, California State University San Marcos, San Marcos:Research paper DS1, 27p.–Research paper DS1, 27p. http://eudml.org/doc/120722.

---

31. It is necessary to provide an argument that this list of cases is complete! That is, that every element of the universe falls into one of the cases.↩

32. http://en.wikipedia.org/wiki/Four_color_theorem↩

33. http://en.wikipedia.org/wiki/Goldbach↩

34. This conjecture was discussed previously in the exercises of Section 1.2↩

35. This question was problem A4 in the 63rd annual William Lowell Putnam Mathematics Competition (2002). There are three collections of questions and answers from previous Putnam exams available from the MAA, Gleason, Greenwood, and Kelly (2003), Alexanderson, Klosinski, and Larson (1985), Kiran S. Kedlaya and Vakil (2002)↩