You probably have heard about the following brainteaser :

Consider a $8\times 8$ chessboard. Remove two extreme squares (top-left and bottom-right e.g.). Can you fill the remaining chessboard with $1\times 2$ dominoes ?

The answer lies in a coloring argument. The problem, however, does not use the fact that the chessboard is colored. I would like to know improved examples of coloring problems like this one.

For instance, could you extend the problem with Tetris-like L-shaped dominoes and solve it using more than two colors ?

  • $\begingroup$ Well, with 2x3 "dominos" you notice that 6 doesn't divide 64... $\endgroup$ Jul 30 '12 at 16:44
  • $\begingroup$ 2x3 means L shape. $\endgroup$
    – vanna
    Jul 30 '12 at 16:45
  • $\begingroup$ Could you clarify: When you talk about using Tetris pieces, you are talking about an ordinary chessboard, not one with two pieces removed? $\endgroup$ Jul 30 '12 at 16:55
  • $\begingroup$ @SiliconCelery : as you can add two L-shaped dominos to get a 2x4 rectangle, they can fit a regular chessboard. Concerning my question I guess the problem should be different from the beginning, it should probably substract each of the extreme squares to get 60 = 15 x 4 squares $\endgroup$
    – vanna
    Jul 30 '12 at 17:01
  • 1
    $\begingroup$ The 35 hexominoes cannot be packed into a rectangle as you have two more squares of one color than the other. See en.wikipedia.org/wiki/Hexomino. I have seen many math puzzles that exploit coloring. For trominoes you often color in strips of three colors or diagonally like a checkerboard with three colors. $\endgroup$ Jul 30 '12 at 17:59

Solomon Golomb's book Polyominoes presents a number of arguments of this type.

One that I remember is: a square is deleted from an 8×8 checkerboard. Can the remaining 63 squares be covered by 21 1×3 rectangles? The answer involves coloring the checkerboard in three colors in alternating diagonal stripes:

colored checkerboard

This colors the 64 squares of the checkerboard with 21 green squares, 21 yellow squares, and 22 blue squares. Each 1×3 rectangle must cover exactly one square of each color. The deleted square therefore cannot be any of the green or yellow ones, nor any of the squares equivalent to one of these under a rotation or reflection of the checkerboard:

Solutions must look like this

(This is four copies of the first diagram, superimposed, with suitable rotations.)

This eliminates all but 4 squares from consideration, namely the four bright blue ones in the previous diagram. So the only solutions involve deleting one of these four blue squares.

There are a number of analogous arguments about polyhexes that depend on a three-coloring of a hexagonal lattice:

hexagonal coloring

For example, there are three different trihexes, which are made by joining three hexagons; two of these are guaranteed to cover exactly one cell of each color, no matter how they are placed.

I once wasted a lot of time trying to make myself a set of tetrominoes by marking up a 4x5 rectangle and cutting it apart, and I felt rather foolish when I realized that a straightforward checkerboard coloring shows that this is impossible. There are 5 tetrominoes, and four of them must cover two black and two white squares each. The 5th is T-shaped, and must cover three black squares and one white (or vice versa).

tetromino coloring

So they cannot possibly tile a 4×5 rectangle, which has equal numbers of black and white squares.

  • $\begingroup$ Very nice example of coloring pattern. $\endgroup$
    – vanna
    Jul 30 '12 at 19:38

A woodworm is sitting at the centre of a cube that's divided into $3^3$ identical cubelets. The woodworm can go from the centre of one cubelet to the centre of another in any edge-parallel direction. The woodworm would like to eat its way through the cube such that it visits the centre of each cubelet exactly once. Is this possible?

  • $\begingroup$ Same principle, I see. Awesome ! $\endgroup$
    – vanna
    Jul 30 '12 at 19:06

I searched for math.SE questions and answers that involve colouring of tilings and the like; here are two interesting ones that I found:

The Mathematics of Tetris

A tiling puzzle/question


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.