10 - Adventures in Tiling and Coloring

Summary

“What's the color got to do with it?”

“It's got everything to do with it. Illinois is green, Indiana is pink.

“Indiana PINK? Why, what a lie!”

“It ain't no lie; I've seen it on the map, and it's pink.”

Mark Twain Tom Sawyer Abroad

There are many lovely proofs in which the tiling of regions and the coloring of objects appear. We have seen examples in earlier chapters, such as tiling in the proof of Napoleon's theorem in Section 6.5, and coloring in the proof of the art gallery theorem in Section 4.6. Tiles enable us to compare areas without calculation, and color enables us to distinguish relevant parts of figures easily.

In this chapter we continue our exploration of elegant proofs that employ these techniques. We begin with a brief survey of basic properties of tilings, followed by some results using tilings with triangles and quadrilaterals, including the Pythagorean theorem. We also discuss the lovely tilings found in the Alhambra in Granada, Spain, and in the work of M. C. Escher. After visiting the seven frieze patterns, we examine the use of color in proofs, and proofs about colorings. Our examples include tiling chessboards with polyominoes, packing calissons into boxes, map coloring, and Hamiltonian circuits on dodecahedra.

Plane tilings and tessellations

A tiling of the plane is any countable family of closed sets (the tiles) that cover the plane without gaps or overlaps [Grünbaum and Shephard, 1987].