Season 4 Episode 0

Can we cover an 8 by 8 square with 32 dominoes (2 by 1 rectangles)? Yes we can! What if we remove two corners? In this episode we solve this problem and some variants.

Further Reading

Chessboard problems

In the livestream, we came up with the hypothesis that if one of $m$ and $n$ is odd and the other is even, and we remove opposite corners of an $m$-by-$n$ rectangle, then we can tile the remaining shape with dominos. We didn’t prove this on the livestream, but you might like to try to prove that yourself before we discuss it in the next livestream.

Parity

This livestream introduced the idea of parity. Someone in chat asked for another example and I gave quite a strange example involving eggs. Later that day, I came across a much more normal example; a friend told me that they’d been for a swim and their smartwatch had tracked 63 lengths, but they knew that was wrong because they ended the swim at the same end of the pool that the started at. A proof by parity argument in real life!

The idea of parity can be used for error detection in computer communication. The idea is that I’d like to send you lots of binary numbers but it’s a slightly noisy line and any particular digit might get switched. We could agree that I’ll send you seven digits at a time, and every eighth digit instead of sending you data, I’ll send a digit that makes sure that the sum of that eight-digit group is even. Then when you receive my message you can check the parity of each eight-digit group; if it’s odd then there must have been a mistake introduced in transmission. Of course, there are some problems with this; you won’t know what the error was, you can’t detect two errors in the same eight-digit bit, and we’re now spending 12.5% of our time communicating parity checks rather than actual data.

For a more advanced error correction code, you might like to find out about Reed-Solomon codes; Computerphile video here.

Chess puzzles

I don’t know a lot about chess, but I understand that in chess puzzles the idea of a “parity argument” comes up in puzzles that ask you to look at a chessboard and work out whose turn it is (see e.g. this website). Note that it’s not always possible to look at a chessboard and decide whose turn it is; consider a board where one white pawn and one black pawn have each moved two squares forwards. We can’t say whether those pawns moved one square at a time each, or if one of them moved two squares at once.

Induction for tiling problems

We didn’t solve the chessboard problem with induction, but we did use induction for a similar problem about a year ago. Back in Season 2 Episode 12 “A few more things”, one of the things that we included was a tiling problem which asks for the number of ways to cover a $2\times n$ board with $2\times 1$ dominoes. We approached that with induction in the livestream, and then the further reading goes through a more complicated calculation for a $3\times n$ board.

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.