Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You probably have heard about the following brainteaser :

Consider a 8×8 chessboard. Remove two extreme squares (top-left and bottom-right e.g.). Can you fill the remaining chessboard with 1×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 ?

share|improve this question
    
Well, with 2x3 "dominos" you notice that 6 doesn't divide 64... –  Chris Taylor Jul 30 '12 at 16:44
    
2x3 means L shape. –  vanna Jul 30 '12 at 16:45
    
Could you clarify: When you talk about using Tetris pieces, you are talking about an ordinary chessboard, not one with two pieces removed? –  SiliconCelery Jul 30 '12 at 16:55
    
@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 –  vanna Jul 30 '12 at 17:01
1  
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. –  Ross Millikan Jul 30 '12 at 17:59

3 Answers 3

up vote 12 down vote accepted

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.

share|improve this answer
    
Very nice example of coloring pattern. –  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?

share|improve this answer
    
Same principle, I see. Awesome ! –  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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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