Coloring (Parity Arguments)

Coloring is a technique in combinatorics that can be used to solve board-tiling problems, specifically to prove certain tilings are impossible. Generally, one assigns a specific color or label to each square on a board and shows that the tiles cannot satisfy constraints set by the coloring.

Examples and Problems

Suppose one has an 8-by-8 chessboard, and one wishes to tile it with 1-by-2 dominoes. This is certainly possible, by simply placing 4 dominoes horizontally in each row.

Now, suppose the top right hand corner square of the chessboard has been removed. Is it still possible to tile the board with dominoes? No: each domino covers two squares of the board, so the total number of squares covered by any tiling must be even, but there are 63 squares in the "mutilated chessboard."

Additionally, suppose the bottom left hand corner square of the chessboard has been removed. Is it still possible to tile this chessboard (which now has two antipodal corner squares removed)? Unfortunately, a parity argument will not work as before, since there are now 62 squares. This will take a clever insight.

Consider the mutilated chessboard in the image below. Is it possible to tile this board entirely with 31 1-by-2 dominoes?

Two antipodal corner squares have been removed from this board. Is it still possible to tile it with dominoes?

We color the board as shown in the picture, alternating white and black squares. Any domino placed on the board will cover exactly one white square and exactly one black square. Thus, for any tiling of the board by dominoes, the number of white squares covered equals the number of black squares colored.

The mutilated chessboard has 32 white squares and 30 black squares, since the two antipodal corner squares have been removed. If there were a covering of this board with dominoes, then the implication would be that 32 equals 30, which is absurd. Thus, it is impossible to tile the board with 1-by-2 dominoes. \(_\square\)

The chessboard coloring from above permits a generalization that solves the following problem:

Given an \(m\)-by-\(n\) rectangular board, can it be tiled by \(1\)-by-\(p\) dominoes (where \(m\), \(n\), and \(p\) are all positive integers, and \(p\) is prime)?

Choose \(p\) colors, labeled \(1\) through \(p\). Color the first row of the board \(\{1, 2, \cdots, p, 1, 2, \cdots, \}\), the second row \(\{2, 3, \cdots, p, 1, 2, \cdots\}\), the third row \(\{3, 4, \cdots, p, 1, 2, \cdots\}\), etc.

By this construction, any \(1\)-by-\(p\) domino must cover precisely one tile of each color. Hence, if the board can be covered by the dominoes, there are an equal number of squares of each color. This implies \(p\) divides \(mn\). Since \(p\) is prime, it follows \(p\) divides \(m\) or \(p\) divides \(n\).

Conversely, if \(p\) divides \(m\) or \(n\), then one may fill out each (without loss of generality) row with dominoes, and hence it is possible to tile the entire board.

Thus, the criterion is that the tiling is possible if and only if \(p\) divides \(m\) or \(p\) divides \(n\). \(_\square\)

However, in some situations, a more complicated coloring will be necessary.

Is it possible to tile a \(10\)-by-\(10\) board with \(1\)-by-\(4\) dominoes?

Choose \(4\) colors, labeled \(1\) through \(4\). Color each odd-numbered row of the board with \(\{1,2,1,2,\cdots,1,2\}\), and each even-numbered row with \(\{3,4,3,4,\cdots,3,4\}\).

By this construction, any \(1\)-by-\(4\) domino must cover an even number of squares of each color. Hence, if the board can be covered by the dominoes, there are an even number of squares of each color. But there are precisely 25 squares of each color; contradiction! \(_\square\)

Here is another problem that uses the idea of a coloring solution for easy visualization:

Coloring problems are, I think, one of the most elegant ways of visualising a problem, that might otherwise be impossible or increasingly difficult to handle.

Here I present a problem, and my coloring solution that really lifted my spirits.

The problem was something like this:

On a \(9\times 9\) grid, two squares are said to be neighboring if they share a common side. There are 65 bugs, each occupying a single square. At \(t=0,\) each bug moves to any of the neighboring squares of the square it was previously in. After \(t=0,\) each of the bug moves into a square that is to the right of it, or to the left of the square it is presently in. The orientation of the bug, is decided in the following way: Suppose a bug is at the square \(A\) at first, and at \(t=0,\) it decides to move into square \(C\) (It could have moved to \(B\) or \(I\) or \(F\) as well at \(t=0\)). The head of the bug is shown by the pointer at its tip. Now it is facing east and it has two options, either to move to \(D\) or to \(E\), which are to the left and right of it at this moment.

(Note that the initial position of the pointer of the bug is pointed towards \(B\) but then it decides to go towards the right; this is because at \(A\) its choices are totally random, so it can actually go to any of the neighboring squares.)

We need to prove that at some point of time \(t,\) there will exist a square containing more than one bug.

Solution

First we begin by noting that by the given move scheme, the bug will be on \(H\) or \(D\) or \(E\) or \(G\) square after 2 moves. So after 2 moves, the bug will have moved one place along a diagonal in any direction.

According to that scheme here is my coloring: We set the notation by defining that the set of all squares colored red is \(R\), that consisting of orange colored squares is \(O\), and correspondingly \(Y\) and \(G\) for those containing yellow and green colored squares.

We note that all the bugs from \(R\) will migrate to \(O\) after 2 moves and vice versa, and all the bugs from \(Y\) will migrate to \(G\) after 2 moves and vice versa.

So we have by our colouring \(|R|=25, |O|=16, |Y|=20, |G|=20.\) Now by the Pigeonhole Principle we have that there are 65 bugs and 4 kinds of coloured squares they can be put in.

So there are at least \(17\) bugs all of which occupy squares of the same color.

In the next two cases we are going to talk about these \(17\) bugs exclusively.

Case 1

If they are all initially in \(O\), then we are done, because 17 bugs in 16 squares ensures more than one bug in at least one square by the pigeonhole principle.

Case 2

If all of them are initially in \(R\), then after 2 moves all \(17\) will be in \(O\), whence we are done again by the pigeonhole principle as in Case 1.

Another case can happen for which we make the following couple of observations.

After one move, a bug from \(R\) or \(O\) will always land in \(Y\) or \(G\).

Case 3

So, in the third case, we apply the pigeonhole principle in the following way:

We have 65 bugs and two classes of colored squares: \(A\) (consisting of the squares from \(R\) and \(O\)) and \(B\) (consisting of the squares from \(Y\) and \(G\)). So there must be at least 33 bugs in one of the two classes \(A\) and \(B\).

If the 33 bugs are in class \(A\) then there are a total of 33 bugs in \(R\) and \(O\), so by the pigeonhole principle again, there is at least 17 bugs in one of them, and the first 2 cases ensure that more than one bug can be located in the same square in such cases.

If the 33 bugs are in \(B\) then after one move they will have moved to \(A\), by the observation given above. So after one move we have 33 bugs in A, whence the argument immediately before this ensures more than one bug in one square.

Hence we are done! \(_\square\)

Note: An interesting thing to note from this proof is that we can achieve the goal of having more than one bug in one square after a maximum of three moves. So at \(t=3\) we can actually ensure that there is more than one bug in some square.

That's the beauty of coloring proofs, a way to visualize.