Here we crack a tricky yet simple problem at the intersection of computer science and mathematics. It also gives a lovely insight into how to prove something is impossible.

Statement and understanding

Let’s take a look at the chessboard below.

As a warm-up, can you see how to tile it with 2x1 rectangular and 1x2 rectangular pieces? (Hint: first cover a 2x2 square with two rectangles, and then see how you can scale this to cover an 8x8 square.)

Side note. If you are puzzling on something and stuck, a good idea is to solve a simpler problem. In the above, if you are stuck, try tiling this 4x4 chessboard with rectangles first

Now we make it a little trickier. We do an act of vandalism and cross out one of the squares

Can we still cover the chessboard with 2x1 and 1x2 rectangular tiles? Take a moment to try and figure it out!

No we cannot. That’s because there are an odd number of squares on the chessboard, and when we cover the board with 2x1 rectangles, an even number of squares are covered each time. So, we could place down 32 2x1 rectangles and cover all 64 squares, or place down 31 2x1 rectangles and cover only 62 squares. There’s no possibility we only cover 63 rectangles. Notice that the logic we used said that, every time we put down a new rectangle, an even number of squares on the chessboard were covered.

Finally, what if we cross out to squares on opposite sides? Now things get tricky… try and solve it, and let me know in the comments if you succeeded without peaking at the solution

Mathematics and Invariants

Often in mathematics and computer science, you want to prove something is impossible. This seems quite a tall order! Proving an object exists, well, at least you can physically construct an example (sometimes…!). But how do we prove something doesn’t exist?

The conceptual leap is the idea of invariants. We look at properties which are conserved under some operation.

Let’s see this in action now!

Solving a Simpler Case

We follow the famous educator and mathematician Polya’s advice in How to Solve It. If stuck, try and solve a simpler case first!

We are going to use the number of light and dark squares covered as our invariant. In this simpler case — a 4x4 board — I will go through all the steps. While I do this, see if you can work out how to solve the harder problem of an 8x8 chessboard using similar ideas! Then I will show how to solve the harder case :) — or if you think you’re ready, you can skip ahead to the next section.

For this smaller board, you can see that, excluding the crossed out squares, there are 6 dark squares and 8 light squares.

Now, we put down our first rectangle.

The rectangle covers one dark square and one light square. That leaves 7 light squares, and 5 dark squares untiled. Let’s play a few more moves.

6 light tiles, and 4 dark tiles to go.

5 light tiles to go, and only 3 dark tiles

3 light tiles, and 1 dark tile

2 light tiles to go, and 0 dark tiles. We cannot tile any more of the board

Hmm, okay we seem to have got stuck. Looking back at what we did, every time we placed down a rectangle, one dark tile and one light tile was covered, and at the end there were two light tiles remaining. Perhaps the different number of light tiles and dark tiles we started with was the problem…

Solving the Problem

First note that on our new chessboard, we have 32 light coloured squares, and 30 dark coloured squares.

Next, we identify our invariant. Here my blue squiggle (yes, I am not very coordinated) represents where I put down a 2x1 rectangle.

Can you see that the purple 2x1 rectangle covers one light square and one dark square?

What that means in practice is that, every time we put down a rectangle, the same number of dark squares and light squares have been covered. But with two dark squares covered, there are more light coloured squares than dark ones. To be precise, there are 30 of the former and 32 of the latter. After placing down our first rectangle, there will be 29 dark squares left uncovered, and 31 light squares left uncovered.

Can you see how to finish the proof? Take a second to try and figure it out!

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

Ok, let’s finish the proof. However many rectangles we put down, there will always be 2 more light squares left uncoloured than dark squares (our invariant!). That means we cannot cover the entire board, as, suppose we managed to place down 30 2x1 rectangles, there would be 2 white squares left, but two dark squares would be left uncovered. As each rectangle covers both a light and a dark square, it would be impossible to cover the remaining two squares. Therefore, covering the entire chessboard is impossible.

Afterword

Yes, this was just a cute chessboard puzzle. But you have also learned something subtle and profound. To prove something cannot exist, you can identify some kind of invariant which remains the same under certain operations. If the end state or object has a different value for this invariant than the starting state, then you know the ‘end state’ cannot be created from the starting state using the process.

This idea is seen all across mathematics, from topology and manifolds, to theoretical computer science. I hope you enjoyed your first taste!

Thank you for reading!! If you have any thoughts, comments, corrections or suggestions, please leave them below :) I try to read and reply to every comment. — Ethan