I am currently reading a great book called Fermat’s Last Theorem by Simon Singh. It is the story of Andrew Wiles who devoted many years of his life to solving a mathematical problem which remained unsolved for 300 years before. The book is not so much about the actual math, but the fascinating people and stories around this particular problem. It is written for a larger audience than mathematicians and also explains fundamental concepts like that of a mathematical proof. The author tries to describe the difference between the notion of a proof in math and versus other sciences. He uses a beautiful example which illustrates the nature of a mathematical proof without relying on any knowledge of mathematics. I have had this kind of conversation before and was in desperate need of a simple yet powerful example for a mathematical proof. The other person would say things like “But a theory is only correct until someone finds a counter example”. So I needed an example, one that convinces people of how a mathematical proof leaves no room for doubt. The one presented in this post is what I will use as my go-to example from now on. There are no pre-requisites to understanding it and it can be explained in just a few minutes, perfect for the kind of conversation I described. Hopefully I will remember it next time!
The question is about a chessboard and some dominoes. The chessboard is slightly modified, because two of its edges are missing. The dominoes are colored half black and half white each. As you might have guessed, the question is if one can perfectly cover the chessboard with dominoes. If you try to do it a few times you will find that it seems difficult. If you keep trying you might start to believe that it is impossible. You can ask more people to try it themselves and nobody will find a solution. Does that mean it is impossible? Unless you have systematically tried every possible arrangement of dominoes on the chessboard you cannot be absolutely sure. And that last step from believing it to be impossible to knowing that is impossible requires a mathematical proof. To be clear, trying out all possible arrangement would be a proof in itself but there are simply too many. So how can we be sure?
First, we observe that the original chessboard has fields, cutting out two edges leaves us with fields. Each domino covers two fields, therefore full coverage of the board requires exactly dominoes. What about the colors? A domino covers two adjacent fields which always have a different color. Therefore dominoes will always cover exactly white and black fields on the chessboard. But how many white and black fields does our chessboard have? The removed fields were both black, creating an unbalanced board with black and white fields. A perfectly covering arrangement of dominoes would therefore have to satisfy both conditions, which is not possible. Therefore no such arrangement exists.
I wrote the draft for this post a while back and have spent some time thinking about since then. Now I decided to include a quick remark before publishing it. The example is indeed a good one in the sense that it gives the Aha-moment of a proof to people without requiring mathematical training. For this reason it can be used to illustrate the nature of mathematical proof versus scientific evidence. It is not the ideal however, as the set of possible solutions is finite. The reason we cannot try all of them is because there are too many and the mathematical proof saves us from a large amount of brute force work. This is great, but proofs are even stronger. Theorems often say things about an infinite number of things like all natural numbers. It is fundamentally impossible to test an infinite number of things and a proof is the only way to confirm the theorem. This is why this example might make proofs look weaker than they are and depending on the context another example might be more appropriate. This one is a fun puzzle though!