There is More to Coloring than Colors

摘要

Solomon Golomb gave an elegant proof by induction for tiling a class of checkerboards by trominoes. These are plane figures consisting of three congruent squares of unit area with two squares meeting the third on adjacent edges, as shown on the left in Figure 1. He showed that no matter which single square cell is occupied or removed from consideration in an nxn square grid having side length a power of 2, the remaining n2 -1 squares can be covered by nonoverlapping trominoes [4]. Such a checkerboard is said to be deficient, and the covering of the remaining squares by trominoes yields a tiling of the nxn array.