HMMT-Feb 2018 comb, Problem 3

A $4 \times 4$ window is made out of 16 square windowpanes. How many ways are there to stain each of the windowpanes, red, pink, or magenta, such that each windowpane is the same color as exactly two of its neighbors? Two different windowpanes are neighbors if they share a side.

Solution: For the purpose of explaining this solution, let's label the squares as \[ \begin{array}{llll} 11 & 12 & 13 & 14 \\ 21 & 22 & 23 & 24 \\ 31 & 32 & 33 & 34 \\ 41 & 42 & 43 & 44 \end{array} \] Note that since the corner squares $11,14,41,44$ each only have two neighbors, each corner square is the same color as both of its neighbors (for example, 11,12, and 21 are the same color, 31,41, and 42 are the same color, etc.). This corner square constraint heavily limits the possible colorings. We will now use casework. Case 1: Suppose two corner squares on the same side (without loss of generality, let them be 11 and 14) have the same color (without loss of generality, red). Then $21,11,12,13,14,24$ are all red, and 12 has two red neighbors (11 and 13) so its third neighbor (22) is a color different from red (without loss of generality, magenta). But 22 has two red neighbors (12 and 21), so its other two neighbors (23 and 32)must be magenta. Applying the same logic symmetrically, we find that all four interior squares $(22,23,32,33)$ have the same color. Furthermore, 21 has one magenta neighbor 22 , so 31 must be red. Symmetrically, 34 is red, and by the corner square constraint we have that all the exterior squares are\\ the same color. Thus in general, this case is equivalent to a window taking the following form (with distinct colors $A$ and $B$ ) The number of choices of $A$ and $B$ is $3 \cdot 2=6$. Case 2: No two corner squares on the same side have the same color. Then from the corner square constraint 12 has neighbor 11 of the same color and neighbor 13 of a different color, so its neighbor 22 must be the same color as 12 . Therefore, this case is equivalent to coloring each quadrant entirely in one color such two quadrants sharing a side have different colors. (A quadrant refers to the four squares on one vertical half and one horizontal half, e.g. 13,14, 23, 24). If only two colors are used, the window will take the form (with distinct colors $A$ and $B$ ): \[ \begin{array}{llll} A & A & B & B \\ A & A & B & B \\ B & B & A & A \\ B & B & A & A \end{array} \] Again there are $3 \cdot 2=6$ ways to chose $A$ and $B$. If all three colors are used, the window will take the form (with distinct colors $A, B$ and $C$ ) \[ \begin{array}{llll} A & A & B & B \\ A & A & B & B \\ C & C & A & A \\ C & C & A & A \end{array} \] or $A A B B$ $A A B B$ $B B C C$ $B B C$ There are $3 \cdot 2 \cdot 1=6$ ways to select colors for each of these forms. Therefore, there are 6 colorings in Case 1 and $6+6+6$ in Case 2, for a total of 24 colorings. $\fbox{24}$.

Answer: 24