What Proof Is Best?

“You don’t have to believe in God, but you should believe in The Book.”

— Paul Erdős

Creating gods in our own image is a human tendency mathematicians aren’t immune to. The famed 20th century mathematician Paul “Uncle Paul” Erdős, although a nonbeliever, liked to imagine a deity who possessed a special Book containing the best proof of every mathematical truth. If you found a proof whose elegance pleased Erdős, he’d exclaim “That’s one from The Book!”

I’m a fan of Erdős, but today I’ll argue that the belief that every theorem has a best proof is misguided.¹

Nowadays there’s a terrestrial shadow of Erdős’ celestial book, called “Proofs From THE BOOK”, and its authors Martin Aigner and Günter Ziegler explicitly disavow the idea that each theorem has a best proof. Their very first chapter contains six different proofs of the existence of infinitely many prime numbers. Ziegler, in an interview in Quanta Magazine, said: “There are theorems that have several genuinely different proofs, and each proof tells you something different.” Most mathematicians (and maybe even Erdős himself) would agree.

A PROBLEM ABOUT TILINGS

A great illustration of this “Let a hundred proofs bloom” point of view is provided by an article by Stan Wagon called “Fourteen Proofs of a Result About Tiling a Rectangle”. Here’s the result his title refers to (a puzzle posed and solved by Nicolaas de Bruijn): Whenever a rectangle can be cut up into smaller rectangles each of which has at least one integer side, then the big rectangle has at least one integer side too. (Here “at least one integer side” is tantamount to “at least two integer sides”, since the opposite sides of a rectangle always have the same length.)

A tiling means a dissection with no gaps or overlaps. Here’s a picture of the sort of tiling we’re talking about (taken from Wagon’s article). 

We see a big rectangle tiled by small rectangles, where each of the small rectangles is marked with either an H (to signify that the horizontal side-length is an integer) or a V (to signify that the vertical side-length is an integer). I hope you’ll agree that it’s not obvious at all that the big rectangle must have an integer side! You might want to play around with the general problem for a bit to convince yourself both that it’s true and that it’s not obvious how to prove it. 

Wagon presents fourteen elegant proofs of this result, contributed by a variety of colleagues; I’ll show you two of them (which can also be found in chapter 29 of Aigner and Ziegler’s book). In both proofs, we call the tiled rectangle R, and we let a and b be the width and height of R, respectively.

I’ll demonstrate, in two different ways, that at least one of the two numbers a, b must be a whole number. You may have an esthetic preference for one proof or the other, but neither of them is dispensable because each of them points in directions that the other doesn’t.

THE CHECKERBOARD PROOF

Divide the plane into ½-by-½ squares alternately colored black and white as in a checkerboard and superimpose this checkerboard with the tiled rectangle, so that the lower left corner of the tiled rectangle is a lower-left corner of a black square in the checkerboard. (Why is the checkerboard coloring relevant and helpful? Why do we want ½-by-½ squares instead of 1-by-1 squares? Wait and see!) I’ll draw the black squares as gray squares to make it easier for you to see the checkerboard and the tiling at the same time.

Here’s a proof that at least one of the two numbers a, b must be a whole number (with some of the details deferred to the Endnotes):

(1) Because each of the rectangles that tile R has an integer side, each tile T contains an equal amount of black and white; that is, the black part of T and the white part of T have the same area. (See Endnote #2 for justification.)

(2) Therefore R (being composed of tiles) contains an equal amount of black and white.

(3) Now ignore the tiles and focus on the a-by-b rectangle R. Suppose a and b aren’t integers. Let m and n be the integer parts of a and b respectively, and write a=m+r and b=n+s, with r and s between 0 and 1. Split R into an m-by-n rectangle, an r-by-n rectangle, an m-by-s rectangle, and an r-by-s rectangle, as in the picture below. Each of the first three rectangles has an integer side and therefore has equal amounts of black and white (as in (1)) but the fourth has more black than white. (See Endnote #3 for justification of that last assertion.)

(4) Therefore R contains more black than white.

(5) Since (2) and (4) contradict each other, our supposition that a and b aren’t integers is incompatible with the assumption that each of the tiles has an integer side.

(For a related approach, see Endnote #4.)

THE TILES-AND-CORNERS PROOF

Draw the standard Cartesian coordinate frame, with horizontal and vertical axes intersecting at (0,0), and superimpose this picture with the tiled rectangle, so that the lower left corner of the tiled rectangle is (0,0). (Why are coordinates relevant and helpful? Wait and see!)

We’ll put a black dot at the center of each tile and a white dot at each tile corner whose x– and y-coordinates are both integers (let’s call a point like this an “integer corner”), and we’ll draw a dashed line from a black dot to a white dot if the black dot is at the center of a tile and the white dot is at one of the four corners of that tile.

The heart of the argument is to count the dashed lines in two different ways, with each way of counting providing different information about the total. One way to count the dashed lines is to consider how many dashed lines emanate from each black dot, and add up those numbers (in the picture above, that would give a 4 and four 2’s); the other way is to consider how many dashed lines come into each white dot, and add up those numbers (in the picture above, that would give five 2’s and two 1’s).

(1) Each tile has 0, 2, or 4 integer corners. (See Endnote #5.) So each black dot has an even number of dashed lines emanating from it.

(2) Therefore the total number of dashed lines, being a sum of even numbers, is even.

(3) Suppose a and b are non-integer, so that (a,0), (0,b), and (a,b) are not integer corners and there are no white dots there. Then the white dot at (0,0) lies on one dashed line (joining it to the black dot in the middle of the lower-leftmost tile) and every other white dot is a corner of either 2 tiles (as shown above) or 4 tiles (as shown below), so each of those other white dots lies on an even number of dashed lines.

(4) The total number of dashed lines is equal to the number of dashed lines passing into (0,0) (which is 1) plus the number of dashed lines passing into the other integer corners (which, being a sum of even numbers, is even). If you add a bunch of numbers, one of which is odd and the rest of which are even, the total is odd, so the number of dashed lines is odd.

(5) Since (2) and (4) contradict each other, our supposition that a and b are non-integer is incompatible with the assumption that each of the tiles has an integer side.

TRICKS AND METHODS

Back in the 1920s, mathematician George Pólya wrote: “An idea that can be used only once is a trick. If one can use it more than once it becomes a method.”

What would Pólya have said about the two proofs of de Bruijn’s theorem that appear above? Is the idea of imposing a checkerboard coloring a trick or a method? What about the two-ways-of-counting idea?

Here are couple of problems you might try to solve using those ideas.

The Mutilated Checkerboard Problem: Consider an 8-by-8 square from which two diagonally opposite 1-by-1 squares have been removed, with total area 64 − 2 = 62. Is there a way to tile it with 31 1-by-2 rectangles (which can be either horizontal or vertical)? See Endnote #6.

The Half-Friendly Party Problem: Someone tells you “I was at a party with 6 other people, and interestingly, each of us was friends with exactly half of the other 6 people.” (Assume that if person A is friends with person B, then person B is friends with person A; also assume that no person is their own friend.) Clearly the person who told you this is a nerd and a bore, but are they also a liar? See Endnote #7.

I’d modify Pólya’s dictum and say that when a trick works in multiple settings, it’s still a trick, but it goes into a big bag containing all the tricks you’ve ever seen, and a “method” you can use when attacking a new problem is rummaging through the bag and asking yourself “Which of these old tricks might solve this new problem?” Part of one’s mathematical education is filling the bag.

Pólya made a brave start at sharing his own personal bag of tricks and his general approach to problem-solving in the book “How To Solve It”, and more recently there was an effort to crowd-source the collation of mathematical problem-solving tricks at tricki.org. Say someone who’s never seen de Bruijn’s theorem before is trying to prove that there’s no way to divide a rectangle that has no integer side-lengths into smaller rectangles that each have an integer side-length, but they’re stuck. If they go to the Tricki main page and click on “What kind of problem am I trying to solve?” and then click on “Techniques for proving impossibility and nonexistence” and then click on “Invariants” and then click on “Elementary examples of invariants”, they can see both of the proofs I’ve just shown you. Unfortunately the search feature of the Tricki site is very primitive, which limits the usefulness of the site. But it’s a start.

WHAT IS BEST?

There’s an episode of “The Office” in which the character Jim Halpert pulls a prank on his deskmate Dwight Schrute by doing a brilliant imitation of Dwight’s picayune pomposity, asking and then answering the nonsensical question “What kind of bear is best?” The question is hilariously idiotic on many levels (Dwight himself declares the question to be “ridiculous” even though it’s an exaggerated version of the sorts of things he himself says). One aspect of the idiocy is that “best” has no clear meaning in this context. If you need a bear that can claw its way through permafrost, you probably want a polar bear; if you need one that can climb a tree, you probably don’t. “What bear is best?” deserves the response “Best at what?” Likewise, the question “What proof is best?” deserves the response “Best for what?” and “Best for whom?”

Let’s tackle “Best for whom?” first. As Ziegler says, “For some theorems, there are different perfect proofs for different types of readers. I mean, what is a proof? A proof, in the end, is something that convinces the reader of things being true. And whether the proof is understandable and beautiful depends not only on the proof but also on the reader: What do you know? What do you like? What do you find obvious?”

The meaning of “Best for what?” requires some elaboration. No problem or theorem is an island, and the theorem we’ve been discussing should be understood not as an isolated puzzle but as part of a family of related problems. For instance, we might go into higher dimensions and consider a tiling of a three-dimensional box B by smaller boxes, each of which has at least one of its three side-lengths being integers. Must at least one of the three side-lengths of B be an integer? The answer is yes, and both the checkerboard proof and the tiles-and-corners proof can be modified to prove this variant of the tiling-a-rectangle problem.

Here’s another variant: Look at a tiling of a three-dimensional box B by smaller boxes, each of which has at least two of its three (non-parallel) side-lengths being integers. Must at least two of the three side-lengths of B be an integer? The answer is again yes, and the checkerboard proof can be adapted to solve this problem — but the tiles-and-corners proof can’t. 

Should we conclude from this that the checkerboard proof is superior to the tiles-and-corners proof? No! Here’s a variant that tiles-and-corners approach handles easily but the checkerboard approach doesn’t: Show that, whenever a rectangle is tiled by rectangles each of which has at least one rational side, then the tiled rectangle has at least one rational side.

Neither of the two proofs of the original theorem supplants the other; each provides insights that the other lacks, and leads in directions that the other can’t.  Wagon considers fourteen proofs in total, and shows that there is no best proof in the bunch; each has limitations as well as strengths.

Once we start to view math problems not as isolated puzzles but as part of a huge interconnected tapestry − a tapestry that the mathematical community is constantly exploring and extending − then we see that the idea of the One Best Proof fails to do justice to the richness of the tapestry. Which proof is best, you ask?  Well, that depends: where do you want to go next in your exploration of the tapestry? If you want to head in this direction, solution A might be good; if you want to go thataway, solution B might be better.

One best proof? Sorry, Uncle Paul; I say “False”. You don’t have to disbelieve in The Book, but you should disbelieve that.

Thanks to Sandi Gubin, David Jacobi, Joel Spencer, Stan Wagon, and Günter Ziegler.

Next month (Feb. 17): Chess with the Devil.

ENDNOTES

#1: Maybe I’m being unfair to Erdős here, but as far as I know he never modified his original view that each theorem has just one Book proof. Then again, Ziegler (in private communication) remarks: “As I remember Uncle Paul, I think it was not important for him to be right, also in this point, but it was important to him to have a good story to tell, and he did.”

#2: We’re going to prove this claim by literally tearing it to pieces, or rather by tearing the rectangle to pieces. For definiteness we’ll focus on the case where the height of the rectangle is a whole number (since the argument for the case where the width is a whole number is essentially the same).

If there’s an x-by-n rectangle in the plane, where x is a real number and n is a whole number, you can tear it into n x-by-1 strips, so IF we can show that each of those x-by-1 strips contains equal amounts of black and white, THEN we’ll know that the whole x-by-n strip does too. (Here’s a picture of what that slicing-up looks like when n is 3.)

Are we done cutting the problem down to size? By no means! If an x-by-1 strip happens to intersect some of the vertical lines of the checkerboard, you can cut that strip into pieces, using the vertical lines of the checkerboard as cut-lines. As before, IF we can show that each of those new sliced-and-diced pieces has as much black as white, THEN we’ll be able to conclude that the whole strip does.

So now we’ve reduced the claim to tiny rectangles that fit between two consecutive vertical lines in the ½-by-½ checkerboard, and that have height 1 (here I’ve blown up the picture for intelligibility):

Since the tiny rectangle has height 1 and the black part in its middle has height ½, it’s clear that the tiny rectangle is half black and hence half white as well. (If you look at this last part of the argument, you’ll see where we need the fact that all the checkerboard squares are ½-by-½.) Rewinding the argument, we’ve shown that 1-by-x slices are half black and half white, and that shows that the n-by-x rectangle is half black and half white.

#3: We want to show that if r and s are between 0 and 1, then an r-by-s rectangle with a black checkerboard square nestled in its lower left corner has more black than white. The most interesting case is when r and s are both bigger than ½, as in the picture. Write r = ½ + t and s = ½ + u, with t and u between 0 and ½. 

The r-by-s rectangle consists of a black ½-by-½ square, a white t-by-½ rectangle, a white ½-by-u rectangle, and a black t-by-u rectangle. So the black area minus the white area equals (½)(½) − (t)(½) − (½)(u) + (t)(u) = (½ − t)(½ − u), which (being a product of two positive numbers) must be positive.

#4: A variant of the checkerboard proof uses the fact that the black area of R minus the white area of R can be written as the product of two numbers, L and M, where L is the black length of the bottom edge of R minus the white length of the bottom edge of R and M is the black length of the left edge of R minus the white length of the left edge of R. (By the “black length of the bottom edge of R” I mean the sum of the side-lengths of the black squares that adjoin the bottom edge of R.  Similarly for the other black and white lengths.) You might check that the punchline of Endnote #3 uses this trick.

#5: Write the corners as (x,y), (x‘,y), (x,y‘), and (x‘,y‘). Suppose the tile has integer width. Then x‘ and x differ by an integer, so either (x,y) and (x‘,y) are both integer corner points or neither one is, and ditto for (x,y‘) and (x‘,y‘). So the number of integer corners of the tile is 0, 2, or 4.  The same conclusion holds in the case where the tile has integer height.

#6: The word “checkerboard” in the name of this classic problem gives away the trick (excuse me, method). The two removed squares have the same color (black, say), so the resulting mutilated board has more white than black squares. On the other hand, if we could tile the mutilated board with 1-by-2 rectangles, then the board would have to contain equal amounts of white and black, since each individual tile does. This contradiction shows that no such tiling is possible.

#7: How many friend-pairs were at the party? For each person x, we can count the number of people at the party who are friends with x, and then add up all those numbers; that should give us the number of friend-pairs times two, since each friend-pair gets counted twice by this method. (If x and y are friends, then y counts as a friend of x and x counts as a friend of y.) So we must get an even number.

But: each of the 7 people is friends with 3 people, and 3+3+3+3+3+3+3 is odd. Contradiction!

#8: I hope to present a version of this essay at the 14th annual Gathering for Gardner in March 2020.

REFERENCES

Martin Aigner and Günter M. Ziegler, “Proofs from THE BOOK”, Springer (Sixth Edition 2018).

Erica Klarreich, “In Search of God’s Perfect Proofs”, Quanta Magazine.

George Polya, “How To Solve It” (1945). For a quick summary of some of the main ideas, look at the handout George Melvin created for a course he taught at Berkeley.

Stan Wagon, “Fourteen Proofs of a Result About Tiling a Rectangle”.