CODING DOMINO COVERINGS:
The following figures (called "domino
coverings") represent various ways to cover a 4x4 sized square with
rectangular tiles of size 1x2 (dominos):
A company that makes hibachis
decided to use these patterns for their steel-mesh grills. The grills fit
on the hibachi's square top in any orientation; either side can be up. The
manufacturing process is highly automated: to specify a grill, just type
its code (such as vvhvvhhh) into the grill-making machine. In a few minutes, out
comes a steel-mesh grill in the shape specified by the code (see first grill in
first row above). After some thought, the engineers decided that there
were only nine different grill designs possible (shown in the second row above).
Is nine the right number? What codes do you type in to get each of the nine
grills shown in the second row?