Coloring arguments: how to know which coloring to use

Every coloring proof reads as though the coloring was obvious. Color the board like a chessboard, notice that each domino covers one square of each color, count, done. One line, and the whole argument evaporates.

What that write-up hides is the only decision that was ever hard: which coloring. You have to choose it before you know it works, and the wrong choice is not a proof that comes out wrong, it is a proof that comes out saying nothing at all. This guide is about making that choice on purpose. The technique itself already has a page at coloring arguments, and the statement is not repeated here.

There is a second thing to sort out first, because it causes more wasted time than any bad coloring does. The word covers two completely different situations. Sometimes you invent the coloring, and it is a tool. Sometimes the problem hands you one, and it is an adversary. They ask for opposite instincts, and the last section is about telling them apart.

Three signals that you should be coloring

• A rigid piece placed on a structured set. Dominoes, trominoes, $1 \times n$ strips, knight moves. The piece never changes shape, so whatever colors you paint, the piece always meets them in a restricted way. That rigidity is the entire engine of the method.
• Everything moves at once, or moves to a neighbor. Tokens stepping to adjacent cells, chips sliding, a tour that must visit every square. Here adjacency is the structure, and a coloring in which adjacency always changes color converts a process into a parity statement you can count.
• A count that comes out clean and still tells you nothing. The mutilated chessboard leaves 62 cells for 31 dominoes, and $62 = 2 \times 31$ passes without complaint. When the obvious count is satisfied but the configuration still smells impossible, you need a finer obstruction, and splitting one count into several that must each balance is exactly what a coloring does.

The rule that picks the coloring

A coloring is not chosen to make the board look nice. It is chosen to make the piece rigid. The requirement is exact, and it is the only thing you need to remember:

Every legal placement of the piece must see the same color profile.

If that holds, the color counts are conserved and any imbalance between color classes kills the tiling. If it does not hold, you have painted a pretty board and learned nothing. So read the piece, not the board.

Two alternating colors work for anything that covers exactly two adjacent cells. On the mutilated chessboard, every domino covers one light and one dark cell no matter where it lands, the two removed corners share a color, and what is left is 32 of one and 30 of the other. Thirty-one dominoes would need 31 of each, so nothing works.

Now keep the coloring and change the piece, and watch it fail.

Watching the wrong coloring fail

Can a $10 \times 10$ board be tiled by twenty-five $1 \times 4$ pieces? Try the chessboard coloring. The board splits 50 and 50. Every $1 \times 4$, horizontal or vertical, covers two of each color. Both sides balance perfectly and you have proved nothing whatsoever.

The reason is worth more than the example. The piece has period four and the coloring has period two, so the piece always sees an average, and averages never obstruct anything. A coloring only bites when the piece cannot smooth it out.

So match the period of the coloring to the length of the piece. Color cell $(i, j)$ with $(i + j) \bmod 4$: four colors in diagonal stripes. Every $1 \times 4$ now covers each of the four colors exactly once, in both orientations, which is precisely the rigidity condition. Twenty-five pieces would therefore need 25 cells of each color. The actual counts on the board are 25, 26, 25 and 24. So no tiling exists.

That is the general move. The chessboard coloring is one member of a family, not a first resort: stripes by rows, stripes by columns, diagonals $(i+j) \bmod k$, blocks, and for awkward pieces a coloring that marks only some cells and leaves the rest blank. The piece tells you which.

The thirty-second test

Before you count anything, place the piece in two or three genuinely different positions and write down its color profile each time. Then one of three things is true.

1. The profile changes. The coloring is dead. You have lost half a minute rather than the ten minutes it takes to discover this inside a counting argument.
2. The profile is constant and the color classes come out equal. Also dead, but differently: the coloring is valid and simply carries no information, like the chessboard on the $1 \times 4$ problem. You need more colors, or a pattern with a different period.
3. The profile is constant and the classes are unequal. Write it up. You are finished.

The same test works when the rigid thing is a move rather than a piece. On the 5 by 5 board where every token steps to a neighbor, a step always changes color, the board holds 13 cells of one color and 12 of the other, and 13 tokens cannot land injectively on 12 cells. Nothing was tiled and the reasoning was identical, because "every move flips color" is what a constant color profile looks like for a process.

When the colors are given to you

Now the other family. A problem that begins "in any 2-coloring of" has already made the choice, and it is not on your side. You are not inventing an invariant; an adversary is painting and you must find structure that survives every possible painting.

Every 2-coloring of the numbers 1 to 9 contains three of one color in arithmetic progression is the small case worth knowing. Nine is sharp, too: some 2-coloring of 1 to 8 avoids it entirely, which is why the problem names 9 and not 8. Two monochromatic triangles in a 2-colored $K_6$ is the same species, settled by counting the pairs of differently colored edges at each vertex.

The recognition tell is the word any sitting next to a coloring in the hypothesis. When you see it, stop looking for a clever palette, because the palette is not yours. Reach for pigeonhole, extremal choices and systematic case-work instead.

Held side by side the difference is clean. In the invent family, the coloring is your move and the conclusion is impossibility. In the given family, the coloring is the opponent's move and the conclusion is that something must exist anyway. Knowing which room you are in is most of the work.

What to do with this

Do not solve ten tiling problems. Take ten, and for each one write two lines only: a candidate coloring, and the piece's color profile under it. Run the thirty-second test and move on. You will get through all ten in the time one full write-up takes, and choosing the coloring is the part you are actually short of.

Lemma teaches this as a named technique with the invariant behind it, rather than as a chessboard trick you meet twice and forget. The coloring arguments page has the statement and where it sits in the curriculum, the problem archive has the problems above in full with difficulty and expected time, and the daily problem posts a new one every day in three tiers, no account needed.