2018 AMC 10A Problem 20

P16-20~6 minPrint

Paths & Grids Basic Counting Transformations & Symmetry Map the objects to something easier to count Exploit symmetry to reduce work or pair up objects

A scanning code consists of a $7 \times 7$ grid of squares, with some of its squares colored black and the rest colored white. There must be at least one square of each color in this grid of $49$ squares. A scanning code is called $\textit{symmetric}$ if its look does not change when the entire square is rotated by a multiple of $90 ^{\circ}$ counterclockwise around its center, nor when it is reflected across a line joining opposite corners or a line joining midpoints of opposite sides. What is the total number of possible symmetric scanning codes?

Show solution without answering

Key insight

All the rotations and flips together fold the grid onto one triangular slice, one-eighth of the square, holding 10 cells. Color those freely: 2^10 ways, minus all-black and all-white.

Solution

A symmetric code looks the same after every rotation and every flip. So once you color a few cells, all the cells they get moved onto must have the same color. The job is to find how many cells you can choose freely.

1. Set up labels. Put the center cell at $(0, 0)$ and label each cell by how far it is right and up from the center, from $-3$ to $3$ in each direction.
2. Which cells must match? Rotating by $90^\circ$ and flipping across the middle lines and diagonals can move a cell $(x, y)$ to any cell whose two coordinates are the same two sizes, in either order and with any signs. For example, $(3, 1)$ must match $(1, 3)$ , $(-3, 1)$ , $(3, -1)$ , $(-1, -3)$ , and so on: $8$ cells in all.
3. Pick one cell from each matching group. Every group has exactly one cell with $0 \le y \le x$ . These cells form a triangular slice, one-eighth of the square:
- $x = 0$ : $(0,0)$ . $1$ cell.
- $x = 1$ : $(1,0), (1,1)$ . $2$ cells.
- $x = 2$ : $(2,0), (2,1), (2,2)$ . $3$ cells.
- $x = 3$ : $(3,0), (3,1), (3,2), (3,3)$ . $4$ cells.

That is $1 + 2 + 3 + 4 = 10$ cells.
4. Count the colorings. Each of the $10$ cells can be black or white, and the choice for the slice decides the whole grid. That gives $2^{10} = 1024$ symmetric grids.
5. Remove the one-color grids. The code must use both colors, so take away all-black and all-white: $1024 - 2 = 1022$ .

The answer is $\boxed{\textbf{(B)}\ 1022}$ .

Why this works

When a pattern must look the same under several moves, cells that the moves carry onto each other are tied together and must share a color. Count the groups of tied cells, not the cells. The four rotations and four flips of a square cut it into eight matching slices, so one slice (with its edges) holds exactly one cell from each group. The "at least one of each color" rule is a small subtraction at the end.

Alternative approach

Check the count of $10$ groups by adding up group sizes. The center is alone ( $1$ cell). Each cell like $(1,0)$ on a middle line is tied to $4$ cells, and there are $3$ such groups ( $12$ cells). Each cell like $(1,1)$ on a diagonal is tied to $4$ cells, $3$ groups ( $12$ cells). The cells $(2,1)$ , $(3,1)$ , $(3,2)$ each lead a group of $8$ ( $24$ cells). Total $1 + 12 + 12 + 24 = 49$ , the whole grid, in $1 + 3 + 3 + 3 = 10$ groups.

Concise solution

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

The required symmetries (four rotations and four reflections) are all the symmetries of a square. A symmetric code is determined by the colors in one fundamental wedge: the triangle bounded by a vertical line through the center and a diagonal, one-eighth of the grid. Every other cell is carried onto a wedge cell by some symmetry and must match its color.

Count the wedge cells with the center at $(0,0)$ and coordinates $-3 \le x, y \le 3$ . Choose the wedge $0 \le y \le x$ :

$x = 0$ : $(0,0)$ , the center. $1$ cell.
$x = 1$ : $(1,0), (1,1)$ . $2$ cells.
$x = 2$ : $(2,0), (2,1), (2,2)$ . $3$ cells.
$x = 3$ : $(3,0), (3,1), (3,2), (3,3)$ . $4$ cells.

That is $1 + 2 + 3 + 4 = 10$ independent cells, each freely black or white, so $2^{10} = 1024$ symmetric colorings.

The code must use both colors, so remove the all-white and all-black grids: $1024 - 2 = 1022$ .

The answer is $\boxed{\textbf{(B)}\ 1022}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Introduction to Geometry, Chapter 16: The More Things Change. . . (§16.1, §16.2, §16.3, §16.4)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)