Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
''Looks exactly the same from all sides'' means that the coloring is the same if we rotate the square? –  Beni Bogosel Dec 10 '11 at 11:43
    
@Beni Bogosel:I believe that's correct interpretation. –  Quixotic Dec 10 '11 at 11:51
    
Can adjacent small squares have the same color? –  mjqxxxx Dec 10 '11 at 13:04
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$ –  Ross Millikan Dec 10 '11 at 15:39

2 Answers 2

up vote 12 down vote accepted

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

share|improve this answer

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

share|improve this answer
    
+1. This was the way I got started as well before resorting to the recurrence argument to be completely sure. –  user17762 Dec 10 '11 at 13:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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