My Favorite Math Problem

Summary

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