2018 AMC 12A Problem 15

Problem 15 of 25IntermediateCombinatorics Problem-Solving Techniques

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 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

Solution

Under the symmetry group of the square, the

49

cells break into orbits, and every cell in an orbit must have the same color. Give a cell coordinates

(i,j)

relative to the center, where

-3\le i,j\le3.

Rotations and reflections can change signs and interchange the coordinates, so each orbit has one representative with

0\le i\le j\le3.

There are

1+2+3+4=10

such pairs. Each orbit is black or white, giving

2^{10}

colorings, but the all-black and all-white grids are excluded. So there are

2^{10} - 2 = 1022

symmetric scanning codes. Thus, the correct answer is B.

AoPS wiki

Tagged: symmetry · basic counting

Answer choices

Solution

More practice