Having studied quite a bit of math, I have done a ton of problems. And when you do enough of anything, you develop a taste for things. I love good problems. I also enjoy sharing them with people. There is one I find particularly good — actually, in many ways, it's the best one I know.
The statement is quite simple: Consider a normal chessboard. Produce a mutilated chessboard by removing two opposing diagonal corner squares (illustrated below).
Now, it's clear that a normal chessboard can be covered by 2x1 blocks. The question then is the following: Can a mutilated chessboard be covered using (exactly 31) 2x1 blocks?
Just to clarify further: This is a yes or no question. The question is not how the mutilated chessboard can be covered; the question is if this can be done at all. Clearly, one way to answer the question in the affirmative is to actually produce a covering: If a covering were successfully produced, then yes, of course, a covering exists. The point is, though, that an argument that either proves the existence of a covering or a nonexistence of any covering is enough,
Canonical solution below:
The answer is no. No covering by 2x1 blocks exists for the mutilated chessboard. The mutilated chessboard contains 32 white squares and 30 black squares. A 2x1 block always covers two squares of different color, hence they cannot be arranged to cover a board with different number of white and black squares.
Now, why do I like this problem so much? Well, for one, it's simple. You could explain this to a 7-year-old, and they would probably get the gist of it. And even though it's simple, it's very difficult. This is subjective, of course, but I find that this is common with these kinds of combinatorial problems. They are easy to state, the solutions are easy to understand — and yet, coming up with the solution on your own is often extremely hard.
There is, however, a wider context where this problem fits quite well. I think this problem is a way to deliver a pinch of "higher mathematics" in an approachable way. While this is an elementary setting, this illustrates how questions of existence come into play. This is the core: Advanced mathematics is often not about constructing something directly via a calculation or an algorithm, but showing the existence of something. And when you deal with existence, you start to deal with definitions and proofs.
Abstract definitions and proofs about the objects governed by those definitions are interesting in many ways. They can be highly creative, and this is where, I think, math can be compared to art. In particular, understanding and producing definitions and proofs seems to require human intelligence. Amazingly, though, we are right now living a moment where computers are starting to perform in this area.
Modern mathematics is extremely abstract. I would say the shift started somewhere around the late 19th century when Cantor produced breakthrough results in set theory (such as this famous one). Now that this has been going on for a century or two, we are so far down the path of abstraction that at first glance it seems hopeless for a computer to tackle any of this. A fundamental fact, however, is that proofs can be seen as types. Types, on the other hand, are ubiquitous in programming languages. This turns out to be a direction that enables formulation of mathematical theory in a form that computer understands. Microsoft has a project related to the type systems of programming languages. In the hands of mathematicians, it has grown into a project with the lofty goal of formalizing our mathematical knowledge into a computer-readable form. While still highly experimental, this system has already proven itself in serious research.
... continue reading