1.1: Perfect Cover of Chessboards

Here's a silly example of how combinatorics can be used. We're going to cover a chessboard with dominoes, then see how far we can generalize it.

Perfect Cover
Think of a typical chessboard. It's 8 squares by 8 squares in size, with alternating black and white colors. Now think of a pile of dominoes, each of which are big enough to cover exactly two squares on the chessboard. Question: can you completely cover the chessboard with those dominoes, where none of the dominoes hangs off the board? A situation where you can do this is called a perfect cover.

The answer is, yes, of course you can have such a situation, a perfect cover. That seems nice enough. Now let's go a step further and think on a more abstract level.

Discrete Math and Abstraction
Something you're going to discover early on is that in discrete math, things are taken to the abstract a lot. Numbers get replaced with variables, and we discover general patterns behind things. Let's see some of this abstraction in this problem.

You'll also see shortly why this is called discrete math. You're going to find (count) how many ways you can cover arbitrary chessboards. This isn't continuous - you're not finding the way to cover, say an 8x8, 8x8.0001, 8x8.0002, 8x8.003., etc. chessboard. We're using whole numbers here. On a Cartesian (x-y) graph these would be dots, not a line.

Chessboards of m-by-n Size
Let's look beyond 8-by-8 chessboards, and now consider m-by-n chessboards. This kind of "chessboard" is one that could be any number of squares wide by any number of squares - 5x3, 100x100, 7x99, and so on. On what dimensions can you have a perfect cover?

A moment's thinking will lead you to say there's a perfect cover whenever either \(m\) or \(n\) are divisible by 2. More generally, it's when either of these variables are even. (When dealing with discrete math, always remember to generalize and look for more than one answer!) If you do \(m \times n\) you get an even number of squares so you can also say you get a perfect cover if the number of squares is even. This makes sense. Imagine a 3x3 board, the same dimensions as a tic-tac-toe board. You're not going to get a perfect cover on that no matter how much you try. But for any \(m \times n\) board, if either dimension is even, you have a perfect cover.

Clipped Chessboards
Now take a standard 8-by-8 chessboard, and remove the upper-left and lower-right corners. Can you still have a perfect cover?

It turns out you can't. When covering the board, the domino will cover a black square and a white square. Therefore in order to have a perfect cover you need to have an equal number of both colors. When you remove the corners of a chessboard, you remove two of the same color. On the 8-by-8 chessboard, you go from, say, 32 black and 32 white, to 32 black and 30 white. That can't be a perfect cover.

Cliffhanger
Let's generalize. Does this same rule follow for any \(m \times n\) board? Not necessarily. Consider this case: the squares below and to the right of the upper-left corner square are removed. Then it's impossible to have a perfect covering no matter what, because there's no black square available.

At this point, the book stops asking about the dimensions of the chessboard, so we'll do so as well. Instead, it moves on to the domino. What if we change the size of the domino from 2 squares to some arbitrary number b?

b-ominoes

A b-omino is a 1-by-b object that covers a certain number of objects. A 1-omino is a monomio, a 2-omino is a domino, and anything above 2 will just be referred to by its numbers. Here's a 5-omino:

The definition of a perfect cover says the same: the b-ominos must completely cover the board without anything overlapping, falling over the board, and by definition the pieces each cover b spots. When does an \(m \times n\) board have a perfect cover of b-ominoes?

If we go back to the example of  dominoes on a regular chessboard, you can get part of the answer. b must be a factor of m or n. But is this enough? The textbook goes a bit more into detail and considers two cases: when b is a prime number, and when it's not.

Suppose b is a prime number, and you can get a perfect cover of b-ominos on an m-by-n board. Given what we already know, we can assume that b is a factor if \(m \times n\) and therefore a factor of either m or n. 

What if it's not a prime number? We want to show that when we divide m and n by b, we get a remainder for one or both of them. So do the division. You get quotients p and q, and remainders r and s.

$$m = pb + r, \ where\ 0 \le r \le b - 1\\
n = qb + s,\ where\ 0 \le s \le b - 1$$

That sounds weird, so let's use some real-world numbers. Given a 7x8 board and 3-ominoes, divide 7 and 8 by 3. 7 divided by 3 is 2 with a remainder of 1, and 8 divided by 3 is 2 with a remainder of 2. So those equations become:

$$7 = 2 \times 3 + 1\\
8 = 2 \times 3 + 2$$

The goal is to show that r is zero. First we constrain \(r \le s \). If the numbers we're given has an r larger than s - for instance, if the board is 8x7, not 7x8 - just switch the two numbers around. If r = 0, then a perfect cover of the board is possible with b-ominoes.

b-by-b Board with b Colors
At this point we have generalized board size and domino size. We have seen whether or not there can be a perfect cover with these. The last thing we will do is generalize the number of colors on the board. Because this is an example, some constraints will be put on the size of the board and dominoes. Replace the number of colors on the board from 2 to b, the size of the dominoes will be b (so they'll be b-ominoes), and let the dimensions of the board (m and n) both be b. Is there a perfect cover for this?

The board is colored in a specific way. Instead of color names (red, orange, blue...) numbers are used. Note that in this example, the order is 1, b, b-1, all the way down to 2.

So if this were done with \(b = 4\), the top row would be 1, 2, 3, 4; the second row 4, 1, 2, 3; the third row 3, 4, 1, 2; and the bottom row 2, 3, 4, 1.

Taking the board that was just made, make a larger board of size \(m \times n\) using whole copies of this board and also segments of it. This definitely calls for an example. With \(b = 4 \), \(m = 10\), and \(n = 11\), you can get the following board:

Because there are b colors and we're using b-ominoes, each b-omino will cover each color once. Since whole b-ominoes are being used (nothing's hanging off the board) and they cover each color once, there is the same number of each color on the larger board we assembled. Let's divide this bigger board into three sections. Each section has a blue border:

• The upper pb-by-n part (the upper 8x11 part in our example)
• The lower left r-by-qb part (2x8)
• The lower right r-by-s part (2x3)

Recall the equations for m and n from a few paragraphs ago to figure out how these numbers were found, or keep going if you're confident with these things. As a side note, observe that p is how many vertical b-ominoes would be used in each column, r would represent how many uncovered squares remain in the column if only vertical pieces were used, n is how many horizontal b-ominoes would be needed to cover a row, and s is how many uncovered squares would be leftover using only horizontal pieces.

In the upper part, each color appears \(p \times n\) times - in this case, \( 2 \times 11 = 22 \) times. In the lower left each color will be present \(q \times r\) times, which comes out to \( 2 \times 2 = 4\) times.

The question becomes, how many times does each color appear in the lower right area? There are \(r \times s\) squares in the section. Each color appears in a row exactly once, and there are b colors, so there are also \(r \times b) colors in the section. Equate the two:

$$rb = rs$$

If r does not equals zero, we can cancel it from both sides to get:

$$b = s$$

However, this contradicts the condition of \(s \le b - 1\) so it can never happen. r must always be zero. This is the condition needed to have a perfect cover. Our board has a perfect cover.

At this point we have generalized the problem to the point of madness. Because the math has worked out nicely we can conclude that an m-by-n board has a perfect cover if and only if b is a fact of m or n.

Trivial Covers

Define a trivial cover as one where all the b-ominoes are either all horizontal or all vertical. You can say that an m-by-n board has a perfect cover of b-ominoes if and only if it has a trivial cover.

This doesn't mean the only perfect covers possible are trivial covers, just that trivial covers are part of the total possible list of perfect covers.

Fault Lines

The last mental exercise for the section. Imagine a 4-by-4 chessboard perfectly covered with 8 standard dominoes. The task: show that it's possible to divide the board into two horizontal or vertical pieces without cutting through a domino. The line where this cut is made is called a fault line.

Think of it this way: the 4x4 board is composed of two smaller boards which also have perfect covers. Since we don't know the actual dimensions of the two sub-boards, we can just say they are k-by-4 and (4-k)-by-4. 

Now suppose there is a board where there is no fault line. The dominoes are placed on the board in such a way that each of the three vertical lines and each of the three horizontal lines in between the squares are all crossed by at least one domino somewhere. You can't divide this into two sub-boards.

Let \(x_1, x_2, x_3\) be the number of dominoes that cross over each horizontal line from top to bottom. The lack of a fault line means each of these variables has to be positive. Because of the nature of dominoes covering two squares each, each of the x's presented must be even. We get the formula:

$$x_1 + x_2 + x_3 \ge 2 + 2 + 2 = 6$$

Which means there are at least 6 vertical dominoes on the board, because each x counts dominoes. Similarly, we may conclude 6 horizontal dominoes exist. But the initial condition calls for only 8 dominoes. Since \(12 \gt 8\), there is a contradiction. You can't make a perfect cover on a 4x4 board without having some kind of fault line. (Go ahead and try a few times in your head if you're not convinced. Sometimes, playing things out mentally will reveal information.)

Confused Yet?

If you didn't fully understand everything in this section, it's alright. I've spent several days putting this post together, and there are one or two pieces that don't quite make sense to me. Some facts are presented without giving an explanation. You can only fit so much in a textbook. At the end of the chapter there will be problems similar to this one that can be used to work out the ambiguities.