6
$\begingroup$

In how many ways a $4 \times 4$ game board can be colored using four colors (red, green, blue, yellow) in such a way that each small square has a single color and the board looks exactly the same from all sides?

For this particular problem since the board's dimension is $4 \times 4$ we could probably check by brute-forcing but I am inquisitive about how to solve this one for a $n \times n$ board with $n$ or $\space x$ colors?

  • 1
    If the board has to look the same under mirror reflection, as well as rotation, the arguments below give $x^{\frac{n^2}{2}}$ for even $n$ and $x^{\frac{n^2+n}{2}+1}$ for odd $n$2011-12-10

2 Answers 2

13

Let $T(n)$ denote the number of ways of coloring a $n \times n$ board with $x$ colors in such a way that each small square has a single color and the board looks exactly the same from all sides.

Let us now start from the squares which are close to the edges. There are $n$ squares on each side close to the edge. Consider any edge and start coloring from left to right. Each square has $x$ options till the $(n-1)^{th}$ square. However once we color the $n-1$ squares starting from left to right the colors on the other edges are automatically fixed. Hence, the number of ways of coloring the outermost set of squares is $x^{n-1}$. But once we do this, we now need to repeat this procedure for a $(n-2) \times (n-2)$ board.

Hence, $T(n)$ satisfies the recurrence, $T(n) = x^{n-1} T(n-2)$ where $T(1) = x$ and $T(2) = x$.

Hence, $T(2n) = x^{(2n-1) + (2n-3) + (2n-5) + \cdots + 1} = x^{n^2}$ and $T(2n+1) = x^{2n + (2n-2) + (2n-4) + \cdots + 4 + 2}x = x^{n^2 + n + 1}$

7

Each equivalence class of squares under rotation can be colored in $x$ different ways. For even side length $n=2k$, there are $k^2$ equivalence classes of size $4$ (represented by the $k \times k$ squares in the upper left, say); for odd side length $n=2k+1$, there are $k^2+k$ classes of size $4$ (represented by the $k \times (k+1)$ squares in the upper left) and one of size $1$ (the center square). The number of symmetric colorings is therefore $x^{k^2}$ for $n=2k$ and $x^{k^2+k+1}$ for $n=2k+1$.

  • 0
    +1. This was the way I got started as well before resorting to the recurrence argument to be completely sure.2011-12-10