0
$\begingroup$

A 4 × 4 grid of squares is filled in, with each of the 16 squares colored black or white. Two colorings are regarded as identical if one can be converted to each other by performing any combination of flipping, rotating, or swapping the two colors (flipping all the black squares to white and vice versa). How many non-identical colorings are there?

Ok so $2^{16}$ total. How would you go about subtracting the ones that are identical? Any help is appreciated.

$\endgroup$
  • $\begingroup$ Do you know Polya's enumeration formula? $\endgroup$ – Michael Biro Nov 22 '15 at 3:36
  • $\begingroup$ @MichaelBiro I do not $\endgroup$ – jsmith14 Nov 22 '15 at 18:25
0
$\begingroup$

Using Polya's enumeration theorem, we count the number of colorings fixed by each of the rotations, reflections, and color swaps. The number of distinct boards is the average number of fixed boards.

There are $16$ distinct operations, and they each fix the following number of boards:

Fixes all $2^{16}$ boards

  1. The identity.

Fixes $2^4$ boards (defined by a quarter board of $4$ squares)

  1. Rotate $90^\circ$
  2. Rotate $270^\circ$
  3. Rotate $90^\circ$ and reverse colors.
  4. Rotate $270^\circ$ and reverse colors.

Fixes $2^8$ boards (defined by a half board of $8$ squares)

  1. Rotate $180^\circ$
  2. Rotate $180^\circ$ and reverse colors
  3. Reflect
  4. Reflect and reverse colors
  5. Reflect and rotate $180^\circ$
  6. Reflect,rotate $180^\circ$, and reverse colors

Fixes $2^{10}$ boards (defined by a diagonal half board of $10$ squares)

  1. Reflect and rotate $90^\circ$
  2. Reflect and rotate $270^\circ$

Fixes $0$ boards (doesn't move some square and does a color exchange)

  1. Reverse colors
  2. Reflect, rotate $90^\circ$, and reverse colors
  3. Reflect, rotate $270^\circ$, and reverse colors

Therefore, the number of distinct boards is $$\frac{1}{16}(2^{16} + 4\cdot 2^4 + 6\cdot 2^8 + 2 \cdot 2^{10} + 3\cdot 0) = 4324$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.