What it takes to cover a region with no gaps and no overlaps

0:00Here is a grid, four squares down and six across. And here is a tile. It covers exactly two squares, and it can stand up or lie down. The job is to cover the whole grid with these tiles. Nothing left bare. Nothing doubled up. Twenty four squares, two to a tile, so twelve tiles. And there it is. Done. That is not the only way. There are two hundred and eighty one different ways to do it.

0:32Now here is a different grid, and the same question. Try it. Go on. You will get most of the way, and then one square will be left over, on its own, with nothing to pair it with. So you start again. And the same thing happens. After a while you say the thing everybody says: I could not do it. And that is not an answer. Yes and no are not the same kind of claim here. To say yes, you show one arrangement and you are finished.

1:05To say no, you have to rule out every arrangement there could ever be — including the ones you have not thought of. No amount of trying gets you there. Trying harder is not a proof. So let us do something other than try. This grid is five down and seven across. Count the squares: thirty five. Now count what one tile takes. Two. Always two, standing or lying. So two tiles take four. Ten tiles take twenty. Seventeen tiles take thirty four.

1:41Every total you can reach is even. Thirty five is odd. There is no whole number of tiles that reaches it, so no arrangement exists — and I never had to look at a single arrangement to know that. That is what a proof feels like. One line, and the question is closed forever. Counting also tells you when a grid is easy. Look at the four by six again, and forget cleverness.

2:11Stand a tile in the corner. Stand another one under it. That column is full. Do the next column the same way. And the next. The only thing that made it work is that the number of rows was even, so the tiles fill each column with none left over. Even number of rows, any number of columns, and you can always do it. No thought required. Here is where it gets interesting.

2:40Take a grid five down and three across — fifteen squares — and rub one square out. Fourteen squares left. Fourteen is even, so counting has nothing to say. Seven tiles, in principle. I will do that three times, taking out a different square each time. Take out the top right corner. That one can be covered. Take out the middle square of the second row. That one can be covered too.

3:09Now take out the middle square of the top row. And this one will not go. Not once. Not ever. Fourteen squares, an even number, seven tiles — and it refuses. Counting is blunt. It has gone quiet exactly when I need it most. So here is the repair, and it is the strangest idea in this video. I am going to colour the squares. Not because they are coloured. Nothing on this grid is coloured. I am putting the colours there myself.

3:44The rule is only this: no two squares that touch may share a colour. Start in a corner with white, and everything else is forced. Count them. Eight white, seven black. That is all. I have not touched the tiles yet. Now watch what happens to a tile. Lay one down anywhere. It covers two squares that touch. And two squares that touch never share a colour. That was the whole rule.

4:13So this tile takes one white and one black. Turn it. Move it. Stand it up. One white and one black. There are twenty two places a tile can sit on this grid, and I checked every one of them. All twenty two take one of each. There is no way to lay a tile down that dodges this. So seven tiles take seven white squares and seven black ones. That is not a guess. It is forced.

4:42Now go back to the region that refused. The square I rubbed out was the middle of the top row — and look at its colour. It was black. So what is left is eight white squares and six black ones. Seven tiles would need seven of each. Eight is not seven. Six is not seven. And it is finished. There is no arrangement, there never was one, and no one is ever going to find one.

5:11I did not try a single tiling. I counted two colours. Now the honest part, because this is where people go wrong. The colouring rules a tiling out. It never rules one in. Go back to the other two regions. In both of them the square I removed was white. So both are left with seven white and seven black. The counts match. And matching counts prove nothing at all. They only mean this particular argument has no objection.

5:45Here is a region with three white squares and three black ones, all joined together, and it cannot be tiled either. The colours match and the answer is still no. So when the counts agree you are not finished. You are back to hunting. As it happens, the first region has fifteen different arrangements and the second has eight. The third has none. Once you have seen this you start seeing it everywhere.

6:15Here is a board eight by eight, coloured the way boards usually are. Rub out two opposite corners. Sixty two squares left. Even. Thirty one tiles, in principle, and counting has nothing to say. But look at the two corners I took. On this board, opposite corners are always the same colour. So I removed two of the same colour, and what is left is thirty of one and thirty two of the other.

6:45Thirty one tiles would need thirty one of each. Done. In one sentence, for a board with more arrangements than you could check in a lifetime. You might think this is a trick about tiles that cover two squares. It is not. Here is a region of twelve squares, and a tile shaped like an L that covers three. Twelve squares, three to a tile, so four tiles. It can be done — and there is exactly one way to do it. One.

7:18Change the tile to a straight three and it cannot be done at all. Same region. Same number of squares. Different tile, different answer. The two colours are no use here, by the way — there are six of each, and the argument says nothing. That is the lesson, not the trick. Find the thing every tile is forced to do, then count that thing. Let us take the question outside the grid.

7:46Forget the region. Ask which shapes will cover a whole floor, going on forever, with no gaps and no overlaps. Look at what has to happen where corners meet. The angles round that point have to add up to a full turn. A square corner is ninety degrees, and four of them make three hundred and sixty. So squares work. A triangle corner is sixty, and six make a full turn. Hexagons are a hundred and twenty, and three do it.

8:19A pentagon corner is a hundred and eight. Three of them leave a gap and four of them overlap. It misses by a third of a corner, and a third of a corner is as good as a mile. So among regular shapes meeting corner to corner, it is triangles, squares and hexagons, and nothing else. Loosen either of those conditions — let the shape be irregular, or let corners meet edges — and the story opens right up. People are still finding new ones.

8:54So what do you actually take away from this? Not the colouring. The colouring is one trick for one kind of problem. Take this instead. When something will not work, the useful question is never why can I not do it. It is: what does every attempt have in common? Every tile takes two squares — so the total must be even. Every tile takes one of each colour — so the colours must come out equal.

9:23Find the thing that no attempt can escape, and then find a case where that thing is impossible. That is the difference between I could not do it, and it cannot be done. One is about you. The other is about the problem.