2023 AMC 10A Problem 20

P16-20~6 minPrint

Paths & Grids Arrangements with Restrictions Split into exhaustive cases and handle each Exploit symmetry to reduce work or pair up objects

Each square in a $3\times3$ grid of squares is colored red, white, blue, or green so that every $2\times2$ square contains one square of each color. One such coloring is shown on the right below. How many different colorings are possible?

Show solution without answering

Key insight

The center square is in all four 2 by 2 blocks, so pick it first. The four edge-middle squares then use the other three colors, and each corner is forced.

Solution

Start with the square that has the most rules on it, then work outward to the squares with fewer rules.

1. The center. The center square is inside all four $2 \times 2$ blocks. So no other square can have its color. Choose the center's color: $4$ ways. The other eight squares use the remaining $3$ colors.
2. The edge-middle squares. Call them Top, Right, Bottom, Left. Each $2 \times 2$ block contains two of them that are next to each other around the center: Top and Left, Top and Right, Right and Bottom, Bottom and Left. Those two must have different colors. Top and Bottom are never in the same block, so they may match; the same goes for Left and Right.
3. Count colorings of these four squares with $3$ colors. Can all four be different? No, there are only $3$ colors. So at least one opposite pair matches.
- Both pairs match (Top = Bottom and Left = Right): pick a color for Top and Bottom ( $3$ ways) and a different color for Left and Right ( $2$ ways). That gives $3 \times 2 = 6$ .
- Only Top = Bottom: pick their color ( $3$ ways). Left and Right must use the other two colors, one each, in either order ( $2$ ways). That gives $6$ .
- Only Left = Right: the same count, $6$ .

Total: $6 + 6 + 6 = 18$ .
4. The corners. Each corner is in just one $2 \times 2$ block, together with the center and two edge-middle squares next to each other. Those three already have three different colors, so the corner must take the fourth color. No choice is left.
5. Multiply: $4 \times 18 = 72$ .

The answer is $\boxed{\textbf{(D)}\ 72}$ .

Why this works

When squares share rules, fill in the most restricted one first (the center is in every block), then the next most restricted (edge-middles are in two blocks each), and let the least restricted squares (corners, one block each) be decided last. Here the corners turn out to have no choice at all, so all the counting happens in the middle ring.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The center square belongs to all four $2 \times 2$ blocks, so no other square may share its color. Choose the center's color: $4$ ways. The remaining eight squares use only the other $3$ colors.

Label the edge-middle squares $T$ (top), $R$ (right), $B$ (bottom), $L$ (left). Each $2 \times 2$ block contains two of them that are adjacent around the ring ( $T$ with $L$ , $T$ with $R$ , $R$ with $B$ , $B$ with $L$ ), and those two must differ. Opposite squares ( $T$ and $B$ , or $L$ and $R$ ) share no block and may match. So we need colorings of a $4$ -cycle with $3$ colors where neighbors differ:

Both opposite pairs equal ( $T = B$ , $L = R$ , different colors): $3 \cdot 2 = 6$ .
Exactly one opposite pair equal: choose which pair ( $2$ ), its color ( $3$ ), then the other two squares take the remaining two colors in either order ( $2$ ): $12$ .
Neither pair equal: impossible, since $T, R, B, L$ would need $3$ colors with $T \ne B$ and $L \ne R$ and all four neighbors distinct, requiring $4$ colors.

That gives $6 + 12 = 18$ ring colorings.

Each corner lies in exactly one block, together with the center and two adjacent ring squares, all three of different colors; the corner must take the fourth color, so it is forced.

Total: $4 \cdot 18 = 72$ .

The answer is $\boxed{\textbf{(D)}\ 72}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)