Problem:
How many ways are there to place indistinguishable red chips, indistinguishable blue chips, and indistinguishable green chips in the squares of a grid so that no two chips of the same color are directly adjacent to each other, either vertically or horizontally?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
The crucial claim is that the configuration must match one of the two configurations shown below up to a permutation of the colors of the chips and up to a rotation of the board. This implies that the answer is .
Without loss of generality, let the chip in the center square be red. By the adjacency condition, the other two red chips must appear in the corner squares of the grid. There are two possibilities for the positions of these chips: either they are adjacent to the same side or they lie along a main diagonal.
In the first case, without loss of generality, assume that the two remaining red chips are on the top row and that a blue chip is placed in the bottom center square. Then the adjacency condition forces the two remaining squares on the bottom row to be filled with green chips, and the rest of the board is forced.
In the second case, without loss of generality, assume that the two remaining red chips are in the upper left and lower right squares and that a green chip is in the upper right square. Again the rest of the board is forced.
There are two cases to consider: no color is repeated in the middle row or there are two chips of the same color in the middle row. Without loss of generality, if the middle row is (see the figure on the right, above), then there are four possibilities for the middle column: , and . Without loss of generality, if the middle row is (see the figure on the left, above), then there are two possibilities for the middle column: and . That is a total of configurations, and permuting the colors then gives a total of configurations.
The problems on this page are the property of the MAA's American Mathematics Competitions