2012 AMC 10A Problem 20

P16-20~7 minPrint

Basic Probability Arrangements with Restrictions Transformations & Symmetry Split into exhaustive cases and handle each Exploit symmetry to reduce work or pair up objects

A $3 \times 3$ square is partitioned into $9$ unit squares. Each unit square is painted either white or black with each color being equally likely, chosen independently and at random. The square is then rotated $90\,^{\circ}$ clockwise about its center, and every white square in a position formerly occupied by a black square is painted black. The colors of all other squares are left unchanged. What is the probability the grid is now entirely black?

Show solution without answering

Key insight

A spot stays white only if it and the square rotating into it were both white. Corners and edges each cycle in fours; no two neighbours may be white.

Solution

When does a spot end up white? After the turn, each spot holds the square that moved into it. If that square is black, the spot is black. If it is white, it is repainted black whenever the spot used to hold a black square. So a spot stays white only when the square that moved in is white and the square that was there before was white too.
Which squares move where? A quarter turn sends each corner to the next corner, around a loop of four. It also sends each edge square to the next edge square, around another loop of four. The center stays put. These three groups do not affect each other, so find the chance for each and multiply.
Center. It moves onto itself, so it stays white if it was white. It must start black: probability $\frac12$ .
Corners. Number the corners $1, 2, 3, 4$ in the order the turn moves them, so corner $1$ moves to spot $2$ , corner $2$ to spot $3$ , and so on, with $4$ moving back to $1$ . Spot $2$ stays white only if corners $1$ and $2$ were both white. So all four corner spots end black exactly when no two neighbouring corners in this loop ( $1$ and $2$ , $2$ and $3$ , $3$ and $4$ , $4$ and $1$ ) are both white. Count the good colorings by the number of white corners:

White corners	Good colorings	Reason
$0$	$1$	nothing to check
$1$	$4$	any single corner
$2$	$2$	only the opposite pairs $\{1,3\}$ and $\{2,4\}$ ; the other $4$ pairs are neighbours
$3$ or $4$	$0$	some two whites are always neighbours

That is $1 + 4 + 2 = 7$ good colorings out of $2^4 = 16$ , probability $\frac{7}{16}$ .
5. Edge squares. They move around a loop of four in exactly the same way, so the probability is also $\frac{7}{16}$ .
6. Multiply:
$\frac12 \times \frac{7}{16} \times \frac{7}{16} = \frac{49}{512}.$

The answer is $\boxed{\textbf{(A)}\ \frac{49}{512}}$ .

Why this works

A rotation moves the squares around in small loops, and the repainting rule only compares each square with the one that moves into its place. That breaks the nine-square problem into two identical four-square loops plus the center. Once you see the rule is "no two neighbours both white", counting is a short table.

Concise solution

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

After the rotation, a position ends up black if the square that moved there is black, or if the square originally there was black (a white arrival is repainted). So a position stays white only when both it and the square rotating into it were white.

The rotation moves the four corners around in a cycle, moves the four edge squares around in a cycle, and fixes the center. These three groups are independent.

Center: must be black, probability $\frac12$ .
Corners: label them in rotation order $1 \to 2 \to 3 \to 4 \to 1$ . Position $k$ ends white exactly when squares $k$ and $k - 1$ are both white. So all four end black if and only if no two cyclically adjacent corners are both white. Count such colorings: zero whites ( $1$ way), one white ( $4$ ways), two whites that are opposite ( $2$ ways); three or more whites always include an adjacent pair. That is $7$ of the $16$ colorings, probability $\frac{7}{16}$ .
Edges: the same cycle structure, probability $\frac{7}{16}$ .

Multiply:
$\frac12 \cdot \frac{7}{16} \cdot \frac{7}{16} = \frac{49}{512}.$

The answer is $\boxed{\textbf{(A)}\ \frac{49}{512}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 7: Introduction to Probability
Introduction to Geometry, Chapter 16: The More Things Change. . . (§16.1, §16.2, §16.3, §16.4)
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)