2021 AMC 10A Problem 25

P21-25~9 minPrint

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

How many ways are there to place $3$ indistinguishable red chips, $3$ indistinguishable blue chips, and $3$ indistinguishable green chips in the squares of a $3 \times 3$ grid so that no two chips of the same color are directly adjacent to each other, either vertically or horizontally?

Show solution without answering

Key insight

The center touches all four edge squares, so its color's other two chips must go in corners. The empty squares then form paths the other two colors alternate along.

Solution

Name the squares like this:

TL	T	TR
L	M	R
BL	B	BR

The center $M$ touches more squares than any other, so it limits the most. Start there.

1. Say the center chip is red. (At the end, multiply by $3$ for the three possible center colors.)
2. $M$ touches $T$ , $L$ , $R$ and $B$ , so none of those can be red. The other two red chips must go in corners. Corners never touch each other, so any two corners are allowed. Of the $6$ pairs of corners, $4$ are on the same side of the grid and $2$ are opposite each other.
3. Case 1: red corners on the same side, for example $TL$ and $TR$ .
- Square $T$ touches only $TL$ , $TR$ and $M$ , which are all red. So $T$ can take either blue or green without touching another empty square.
- The other five empty squares form a chain $L$ – $BL$ – $B$ – $BR$ – $R$ , each touching the next. With only blue and green allowed, the colors along the chain must alternate: blue, green, blue, green, blue, or green, blue, green, blue, green.
- The first way uses $3$ blues and $2$ greens, so $T$ must be green. The second way forces $T$ to be blue. That is $2$ ways.
- With $4$ choices of side: $4 \times 2 = 8$ arrangements.
4. Case 2: red corners opposite, for example $TL$ and $BR$ .
- The empty squares form two separate chains: $T$ – $TR$ – $R$ and $L$ – $BL$ – $B$ .
- Each chain alternates, so it looks like $X, Y, X$ . To use exactly $3$ blues and $3$ greens, one chain must be blue, green, blue and the other green, blue, green: $2$ ways.
- With $2$ choices of diagonal: $2 \times 2 = 4$ arrangements.
5. With a red center there are $8 + 4 = 12$ arrangements. With any of the $3$ colors in the center, there are $3 \times 12 = 36$ .

The answer is $\boxed{\textbf{(E)}\ 36}$ .

Why this works

Start with the square that touches the most others: its color is forced into the corners. Removing those squares breaks the grid into short chains, and a chain colored with two colors that can't repeat must alternate, so it is fixed once you pick its first color. All that remains is making the color counts come out to $3$ each, which is what separates the two cases.

Concise solution

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

Suppose the center chip is red (multiply by $3$ at the end for the center's color). The center is adjacent to all four edge-middle squares, so the other two red chips must occupy two of the four corners; corners are never adjacent to each other, so any pair of corners is allowed.

Case 1: the two red corners share a side of the grid (4 choices, e.g. top-left and top-right). The top-middle square is then surrounded by red on all three sides and is isolated. The other five empty squares, left-middle, bottom-left, bottom-middle, bottom-right, right-middle, form a path of length $5$ . Coloring a path with blue and green so no neighbors match means alternating, so the path is $XYXYX$ with $3$ of color $X$ and $2$ of $Y$ ; the isolated square takes the third $Y$ . Choosing $X$ gives $2$ colorings. Subtotal $4 \cdot 2 = 8$ .

Case 2: the two red corners are opposite (2 choices, e.g. top-left and bottom-right). The empty squares split into two paths of length $3$ : top-middle, top-right, right-middle; and left-middle, bottom-left, bottom-middle. Each path alternates as $XYX$ ; to use exactly three blues and three greens, one path is $BGB$ and the other $GBG$ : $2$ colorings. Subtotal $2 \cdot 2 = 4$ .

With a red center there are $8 + 4 = 12$ arrangements, so in total $3 \cdot 12 = 36$ .

The answer is $\boxed{\textbf{(E)}\ 36}$ .

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)