Problem:
A board is completely covered by tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the board. Each tile is either red, blue, or green. Let be the number of tilings of the board in which all three colors are used at least once. For example, a red tile followed by a green tile, a green tile, a blue tile, and a green tile is a valid tiling. Note that if the blue tile is replaced by two blue tiles, this results in a different tiling. Find the remainder when is divided by .
Solution:
With colors of tile available there are ways to decide how to color the first square. For each successive square, there are options: one can either extend the current tile, or start a new tile of any of colors. Thus there are a total of colored tilings.
The total number of colored tilings in red, blue, and/or green is thus , which includes the tilings with no green tiles, and similarly for blue and red. By the Inclusion-Exclusion Principle, the number of specified tilings is therefore 8106. The requested remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions