Season 2 Episode 9

Dr Tom Crawford, the Oxford tutor behind the YouTube channel Tom Rocks Maths, presents an interview question that he used last year. Can the people watching live solve it? Find out in this episode.

Links back to Vicky’s episode

I saw some people in chat try to make a link back from the problem Tom set to Vicky’s episode on splitting rectangles into squares – I can’t work out a way to make this work I’m afraid, because the setting back then was that we were splitting a rectangle into lots of squares, whereas in Tom’s problem we’re trying to make a square out of rectangles. But on the other hand, if you like putting shapes together to make other shapes, with some pure mathematics hiding in there, then you’ll love Vicky’s episode!

Tom’s interview question videos

Tom mentioned a couple of videos that he’s made with other Oxford interview questions

Surfaces and volumes of revolution
Prime Reciprocal Series (a very old and very difficult problem!)

Tiling a 2-by-$n$ rectangle

Here’s a different question, which also involves putting 2-by-1 rectangles together to make a shape. This time though, all the little 2-by-1 rectangles are the same size, and we’ll call them dominoes (see the previous episode on dotty maths for some pictures of dominoes, if that’s a new word for you!). We’d like to cover a 2-by-$n$ rectangle with dominoes; without any dominoes overlapping, and without cutting them up, and without going over the edges. Here’s the question; how many ways are there to do that for a 2-by-$n$ rectangle, in terms of $n$?

I’ll tell you the answer in a couple of paragraphs, but you should go away and think about it first. So that you can't just glance down and see the answer, I'll distract you with a different problem instead.

Missing opposite corners

Tom had another problem in mind in case we had extra time in the livestream, which is also about covering a shape with dominoes. Suppose that we’ve got an 8-by-8 grid of squares, and we remove two opposite corners. Can we cover the rest of the grid with 31 copies of a little 2-by-1 rectangle?

I’ll tell you the answer in a couple of paragraphs, but you should go away and think about it first. So that you can't just glance down and see the answer, I'll distract you with the previous problem instead.

Tiling a 2-by-$n$ rectangle again

Are you ready for the answer to the 2-by-$n$-rectangle problem above? OK, here’s the answer. The number of ways to cover a 2-by-$n$ rectangle with dominoes is the $n$th Fibonacci number! (if you count 1 and 1 as the 0th and 1st Fibonacci numbers).

To see why, remember that Fibonacci numbers are defined by $F_0=1$ and $F_1=1$, then $F_n=F_{n-1}+F_{n-2}$ for $n\geq 2$. Here, if we write $a_n$ for the number of ways to put 2-by-1 rectangles together to cover a 2-by-$n$ rectangle, then we’ve got $a_1=1$ (there’s only one way to tile a 2-by-1 rectangle with a 2-by-1 rectangle) and I claim that there’s only one way to cover a 2-by-0 rectangle using zero tiles (maybe that’s controversial, and you think that $a_0$ doesn’t mean anything – in which case, OK, agree that it’s irrelevant to the problem we’re trying to solve and set it to 1 anyway).

Now let’s think about $a_n$ when $n$ is bigger than 1. If we look at the first two squares at one end of the 2-by-$n$ rectangle, then these could be covered by a single domino, or by two dominoes the other way around, which would also cover the next two squares. In the first case, we can continue covering the rest of the shape, and the leftover bit is now a 2-by-$(n-1)$ rectangle. We know how many ways there are to do the rest of the job here; it’s $a_{n-1}$! In the second case, we’ve covered the first two pairs of squares, so we need to cover a 2-by-$(n-2)$ rectangle. There are $a_{n-2}$ ways to do this. Those are all the different ways to cover a 2-by-$n$ rectangle then, and the total number is $a_n=a_{n-1}+a_{n-2}$.

Putting it together, that means that $a_n=F_n$ and the number of ways to cover a 2-by-$n$ rectangle with dominoes is precisely the $n$th Fibonacci number.

Extension: What if we want to cover a 3-by-$n$ rectangle with 2-by-1 rectangles instead? You might find it helpful to also think about the problem of covering a 3-by-$n$-rectangle-with-one-corner-removed at the same time, and you might need to invent a new sequence of numbers, with some sort of definition a bit like Fibonacci numbers. This problem is so interesting that I think I might talk about it on a future OOMC livestream!

Missing corners again

Ready for the solution to the chessboard problem above? Oops, that’s a bit of a hint that I’ve given you there- I’m imagining the 8-by-8 grid as being painted like a chessboard. OK, here’s the answer to the problem with the missing corners above: “no”. To see why, think about painting the squares of the grid alternating black and white in a chessboard pattern, so that no two squares next to each share a colour. Because the removed corners were the same colour, there are 32 squares of one colour and 30 of the other. But any domino we put down will cover exactly one black square and exactly one white square, wherever it is! So we cannot cover all the squares with dominoes.

I really like the proof in the previous paragraph, because it doesn’t need any understanding at all of how to fit the dominoes together. It’s just a fact about something that always happens when you put a domino down. Such a thing (always the same, no matter the configuration) is called an “invariant”. See this page on Brilliant for more examples (log in/sign up required, Oxford is not responsible for content on external sites).

The two-opposite-colours approach here also reminds me of a concept called “parity” which means tracking whether something is even or odd. For example, if you walk around on a chessboard, moving one square up/down/left/right each time, then you can only return to your starting square after an even number of moves (after any sequence of an odd number of moves, you are not at the starting square), because if you start on a white square say, then after an odd number of moves you must be on a black square. That’s an example of a parity argument.

About a year ago, I came up with a problem to do with eggs in eggboxes (it was part of The Big Math-Off, which is a big collection of fun maths articles). There are some special cases that I can do with parity arguments, like the chessboard problem above, but I haven’t solved the general case yet. Maybe there’s a good invariant, but I haven’t spotted it yet.

Extension: What if the two missing squares are different colours (and what if they’re not corners)? Can you tile the rest of the chessboard? The proof above doesn’t tell us anything about this case (it doesn’t tell us that it’s not possible, but that’s not the same as telling us that it is possible- this case might be impossible too for a different reason!). What if four squares are removed?

Curve sketching

I had a discussion with a teacher the other day about whether keen mathematicians in Year 12 or equivalent would be able to sketch a curve like
$$ y = \frac{x^3-4x^2+x+6}{x^2+x-2}$$
Enjoy!

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.