Problem:
A rectangle is partitioned into regions as shown. Each region is to be painted a solid color - red, orange, yellow, blue, or green - so that regions that touch are painted different colors, and colors can be used more than once. How many different colorings are possible?
.jpg)
Answer Choices:
A.
B.
C.
D.
E.
Solution:
There are 5 possible colors for the central rectangle in the lower row. There then are 4 possible colors for the rectangle at the left end of the lower row, then 3 choices for the rectangle at the upper left, then 3 for the rectangle at the upper right, and 3 for the rectangle at the lower right. In all there are possible colorings.
There are ways to paint the regions using all 5 colors. If two regions are painted the same color, then those two regions must be either the upper left and lower right regions, or the upper right and lower left regions, or the lower left and lower right regions. Thus there are ways to paint the regions using four colors. The only way to paint the regions using only three colors is to paint the upper left and lower right regions the same color and the upper right and lower left regions the same color. This can be done in ways. The total is .
Note: This problem can be viewed in terms of chromatic polynomials in graph theory, a concept introduced by George David Birkhoff in 1912.
The problems on this page are the property of the MAA's American Mathematics Competitions