Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section3.5Even more direct 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 lead 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 [10] and the only known value of a Ramsey number for hypergraphs [13].

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 1  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 \(d\). (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 color theorem. The four color theorem is a result known to map makers for quite some time that says that 4 colors are always sufficient to color the nations on a map in such a way that countries sharing a boundary are always colored differently. <<Unresolved xref, reference "fig_Lux_map"; check spelling or use "provisional" attribute>> shows one instance of an arrangement of nations that requires at least four different colors, the theorem says that four colors are always enough. It should be noted that real cartographers usually reserve a fifth color for oceans (and other water) and that it is possible to conceive of a map requiring five colors if one allows the nations to be non-contiguous. In 1977, Kenneth Appel and Wolfgang Haken proved the four color 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, this proof 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. For a good introductory article on the four color theorem see [6].

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  [4] was a mathematician born in Königsberg Prussia, who, curiously, did not make the conjecture 2  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.

Proof

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

Exercise3.5.2

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 randomly 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 <<Unresolved xref, reference "fig_pebbling_move"; check spelling or use "provisional" attribute>>.

—

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.

Exercise3.5.3

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 4 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.

Subsection3.5.1Exercises

  1. Prove that if \(n\) is an odd number then \(n^4 \pmod{16} = 1\). \hint{ While one could perform fairly complicated arithmetic, expanding expression like \((16k+13)^4\) and then regrouping to put it in the form \(16q+1\) (and one would need to do that work for each of the odd remainders modulo \(16\)), that would be missing out on the true power of modular notation. In a “\(\pmod{16}\)” calculation one can simply ignore summands like \(16k\) because they are \(0 \pmod{16}\). Thus, for example, \begin{equation*} (16k+7)^4 \pmod{16} \; = \; 7^4 \pmod{16} \; = \; 2401 \pmod{16} \; = \; 1. \end{equation*} So, essentially one just needs to compute the \(4\)th powers of \(1, 3, 5, 7, 9, 11, 13\) and \(15\), and then reduce them modulo 16. An even greater economy is possible if one notes that (modulo 16) many of those cases are negatives of one another — so their \(4\)th powers are equal. }

  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.) \hint{It is probably obvious that the "cases" will be the possible remainders mod 6. Numbers of the form 6q+0 will be multiples of 6, so clearly not prime. The other forms that need to be eliminated are 6q+2, 6q+3, and 6q+4. }

  3. Show that the sum of any three consecutive integers is divisible by 3. \hint{Write the sum as \(n + (n+1) + (n+2)\).}

  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\). \hint{If there are two pebbles on any node we will be able to reach all the other nodes using pebbling moves (since every pair of nodes is connected).}

  5. Find the pebbling number of a graph whose nodes are the corners and whose edges are the, uhmm, edges of a cube. \hint{It should be clear that the pebbling number is at least \(8\) — \(7\) pebbles could be distributed, one to a node, and the \(8\)th node would be unreachable. It will be easier to play around with this if you figure out how to draw the cube graph “flattened-out” in the plane.}

  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. Show that there are no 2-digit vampire numbers. Show that there are seven 4-digit vampire numbers. \hint{The 2-digit challenge is do-able by hand (just barely). The \(4\) digit question certainly requires some computer assistance!}

  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. \hint{Note that \(15 = 3^2 + 2^2 + 1^2 + 1^2\). Also, if \(15\) were expressible as a sum of fewer than \(4\) squares, the squares involved would be \(1\), \(4\) and \(9\). It's really not that hard to try all the possibilities.}

  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. \hint{The following Sage code generates all the numbers up to \(100\) that can be written as the sum of at most \(3\) squares. var('x y z') a=[s2 for s in [1..10]] b=[s2 for s in [0..10]] s = [] for x in a: for y in b: for z in b: s = union(s,[x+y+z]) s = Set(s) H=Set([1..100]) show(H.intersection(s)) }

  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. \hint{By trichotomy, x is either zero, negative, or positive. If x is zero, its square is zero. If x is negative, its square is positive. If x is positive, its square is also positive.}

  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. \hint{If you know something about determinants it would help here. The determinant will be 0 if there are two identical rows (or columns) in the finished array. Also, if there is a row or column that is all zeros, player Zero wins too. Also, cyclically permuting either rows or columns has no effect on the determinant of a binary array. This means we lose no generality in assuming player One's first move goes (say) in the upper-left corner.}