Patterns

Patterns are the root of math, all else is arithmetic. Unfortunately, most of my early education consisted solely of arithmetic and calculation – that strict application of rules and transformations, imagination not required. That’s not math! And you don’t realize if no one tells you. There’s a certain conspiracy of math professors and teachers of all stripes to re-form elementary math education into a different mold that I hope to give you a taste of here.

Question

Can you cover a chessboard with a set of blocks shaped like a horse move from chess, or equivalently, a four tile L-block from Tetris (if you prefer to think of it that way)?

0
000

The answer is yes. Think for a bit and you’ll see that it’s so. Can you cover any similar rectangle of tiles? To answer this, we consider all possible types of these rectangles by splitting them into three categories.

Case 1: Number of board tiles is not a multiple of four

In the world where your rectangle doesn’t have some multiple of four number of tiles, it is impossible to cover it with Ls. Since each L contains four tiles within it, any set of non-overlapping Ls is going to use a multiple of four tiles (e.g. 2 Ls have 8 tiles, 3 Ls have 12 tiles, and so on).

Among the rectangles ruled out by this case are those with two sides of odd length.

Case 2: Number of tiles is a multiple of eight

We’ll split this case into three types.

case 2a: the one by eight rectangle

00000000

Not happening. You can’t even fit one L on something that narrow.

case 2b: one side is a multiple of four and the other is a multiple of two

We can lay two Ls together to get a two by four shape.

0XXX
000X

By laying many of these on the board with the side of length four oriented with the side of the board that is the multiple of four, the board will be covered without holes. With this trick, we can easily cover the chessboard of the original question.

case 2c: one side is a multiple of eight and the other is odd (but greater than one)

This time we’ll make a more complicated shape; I’ll have to use less pretty letters.

MM0XXXNN
MA000XBN
MAAABBBN

Lay enough of these shapes against the side of the board that is a multiple of eight to cover the entire length. The area of the board that remains uncovered will have one side that is a multiple of eight while the other side will have a length that is an odd less three. An odd less three is even and eight is a multiple of four so the still uncovered board matches the boards that we just tiled in (2b). We’ll use the same trick with the two Ls rectangle shape to cover it.

As a side note, there is a philosophy of mathematics that demands proofs of this type. Sometimes, a mathematician demonstrates that a solution exists by proving that it is impossible for a solution not to exist. To a constructivist, this is a cheat and a shortcut and, as such, unacceptable. Quora has some good examples of these unacceptable proofs.

Case 3: Number of tiles is a multiple of four but not of eight

This is the tricky one. It also turns out to be impossible but it’s non-trivial to sort out why. Bear with me as I sketch the reason.

Each L has four tiles so covering the entire rectangle requires an odd number of Ls. Now break each L into two parts, a horizontal set of two tiles and a vertical set of two tiles. It’ll be impossible to cover the whole with an odd number of horizontals and an odd number of verticals, even ignoring the requirement of connecting them into Ls.

Place all your horizontal pieces. In each row, an even number of tiles has now been taken up. If the width of the board is odd, an odd number of verticals is needed per every two rows and since there are a multiple of four rows, we’ll need an even number of verticals to cover the empty space entire (which makes it impossible). If the width of the board is even, then you need an even number of verticals per row so an even number of verticals entirely (again, impossible).

Continue Questioning, Friends

Hopefully, you’re disappointed that we have an answer so quickly. No reason to stop, the natural question is how we can extend. Well, what about hexagonal tiles? There are L-esque patterns that can be laid there. How about non-rectangular boards of square tiles? The following L shaped board can be covered (do you see?).

000
000
000
000000000
000000000
000000000

What about boards with holes? There are endless variations. Now you have an outlet the next time you’re really bored and staring at a tiled floor. See if you can make some rules and work out a pattern. Then change the rules to make it harder.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s