Little Blue Book Visualized中文

Method line M17 · When and why do we use it?

Coloring and Assigning Values

In the Chinese book: 染色与赋值

Color the cells or give each a number; what a move can change shows up at once.

📖 §4.2 of 《解题方法与策略》

One idea, one pictureThe top-left and bottom-right corners are cut out, leaving 62 cells. Try to cover them with 1×2 dominoes. If you cannot, tap “Checkerboard” and look at the colors of the uncovered cells.

Loading figure…

In one sentence

However you place a 1×2 domino, across or down, the two cells it covers are always neighbors. Color the board as a checkerboard, and neighboring cells always have different colors. So:

Endlessly many tilings, all governed by one sentence. That is what coloring (or giving each cell a number, called assigning values) does: find a marking on which every move has a fixed effect. Then a little counting tells you which things can never be done.

Predict first

Cut the top-left and bottom-right corners out of an 8×8 board, leaving cells. Can dominoes of size 1×2 cover it exactly?

Choose an answer first; then you can see the result.

Example: a board missing two corners

Step 1 / 5
Loading figure…
  1. Count the cells

    With two opposite corners cut out, cells are left. , so the cell count shows no problem.

Notice the power of this proof: we did not try every tiling (there are far too many to count); we counted colors once.

Stop 1 · Coloring (Vol. 7)

A different tile needs a different coloring. A 1×3 strip covers three cells in a row, and the checkerboard cannot control it. Use three colors on the diagonals instead: the color of the cell in row , column is decided by the remainder of on division by . The three cells of a strip have three consecutive values of , so their remainders are exactly , once each.

Example: an 8×8 board with one corner cut out. Can 1×3 strips cover it?

Step 1 / 4
Loading figure…
  1. Count the cells

    cells are left, and . The cell count is fine. Tap some cells and try laying a few strips first.

Think about it: for cells of each color to be left, which color must the cell you cut out be? (And if you cut out the right color, can it always be covered? See the Mistake Museum at the bottom of the page.)

Stop 2 · Operations and games (Vol. 7)

Instead of painting colors, write down a number: that is assigning values. A good assignment keeps a “total” unchanged by every move.

A row of cells is numbered to from left to right, with one piece in each cell. In each move, you choose two pieces, move one of them one cell to the left and the other one cell to the right. Can you get all pieces into the same cell?

Example: can six pieces meet in one cell?

Step 1 / 4
  1. Give each piece a value

    Let the “value” of each piece be the number of the cell it is in. Add up the values of all the pieces and call the total .

Predict first

Change the problem to cells and pieces. The invariant is , and . What does this tell you?

Choose an answer first; then you can see the result.

Stop 3 · Parity arguments (Vol. 6)

A checkerboard coloring is really a picture of parity: color the cell black when is even and white when it is odd.

A classroom has seats, all taken. The teacher asks everyone to move to a seat directly in front of, behind, left of or right of their own. Can it be done?

Example: 25 people all move to a neighboring seat

Step 1 / 4
Loading figure…
  1. The seating plan

    Each cell is a seat. For neighboring seats, “row number + column number” differs by exactly , so the parities are opposite.

What if the classroom is ? There are black and white seats, so parity no longer objects, and it really can be done: in each row, neighbors swap seats (columns 1 and 2 swap, columns 3 and 4 swap), and in the last column the people swap in pairs, front and back.

Practice

Exercise 1Basic

Cut the top-left and bottom-right corners out of a 6×6 board. What is the largest number of non-overlapping 1×2 dominoes you can place on the remaining cells?
Exercise 2Advanced

A row of cells is numbered to , with one piece in each cell. Each move picks two pieces and moves one of them one cell left and the other one cell right. For all the pieces to meet in one cell, the invariant “sum of cell numbers” must be a multiple of . For how many among does this check pass?
Exercise 3Challenge

Cut one cell out of a 7×7 board, leaving cells, to be covered by strips of size 1×3. Color the board with three colors according to “the remainder of row number + column number on division by ” (the top-left cell has row number and column number ). Only cutting out a cell of one particular color gives any hope. How many cells of that color are there?

Mistake Museum · Exhibits from this stop

Before you leave, look at the traps other people fell into here.See every exhibit in the museum →

Exhibit

The color counts match, so it must be possible

The wrong step: Cut the 2nd cell of row 1 out of an 8×8 board and color it with 3-color diagonals: 21 cells each of A, B and C are left. Each 1×3 strip covers exactly one A, one B and one C, so 21 strips can certainly cover it.
What went wrong? Think first, then open

Diagnosis Coloring can only say “impossible”, never “possible”. Equal color counts are only a necessary condition: if the counts are wrong it certainly cannot be done, but if they are right it still might not be. In fact, color it with 3-color diagonals running the other way and that cell gives the game away: this board cannot be covered.

The right step: To prove that something can be done, you must actually do it (give a construction). Coloring proves “impossible”; “possible” takes hands-on work.

“Coloring only ever says no; to say yes, show a tiling”

Exhibit

A coloring that does not suit the tile

The wrong step: An 8×8 board with one corner cut out: can it be covered with 1×3 strips? Color it as a checkerboard: 31 black and 32 white are left. That is close, there is no contradiction, so it can probably be done.
What went wrong? Think first, then open

Diagnosis The checkerboard coloring is made to measure for 1×2 dominoes: each domino covers exactly one black and one white. A 1×3 strip may cover two black and one white, or two white and one black, so for this tile the coloring is not fixed and of course shows nothing.

The right step: When choosing a coloring, first ask: does every tile always cover the same number of cells of each color? For 1×3 strips, color diagonally with three colors so that each strip covers exactly one cell of each color.

“Look at the shape of the tile first, then decide how to color”

Stops on this line

The same idea, used once in each of several places.

  1. ColoringVol. 7 Fun Problems in Combinatorics, ch. 3
  2. Operations and GamesVol. 7 Fun Problems in Combinatorics, ch. 4
  3. Odd and Even NumbersVol. 6 Divisibility, Congruences and Diophantine Equations, §2.4