Hard combinatorics question

• Apr 24th 2013, 12:33 PM
oveluus
Hard combinatorics question
Let's say that I have a chess board (64 squares), and I want to color it using 5 colors (green, red, blue, yellow and black), but making sure that neither of the colors touch each other. How many different boards can I make?

To clarify a bit: let's say that the square b2 is blue. Then the following squares can't be blue: b3, b1, a2 and c2. But the following squares can be blue: a3, c3, a1 and c1.
• Apr 24th 2013, 08:51 PM
chiro
Re: Hard combinatorics question
Hey oveluus.

Are you willing to use a computer to solve this?
• Apr 25th 2013, 06:14 PM
oveluus
Re: Hard combinatorics question
Yes, even though I was hoping for a more general formula.

I know nothing about programming so you'll have to help me with that.
• Apr 25th 2013, 09:13 PM
Kiwi_Dave
Re: Hard combinatorics question
If you colour as follows:

1. colour the lowest left corner
2. colour the 3 squares around that corner
3. colour the 5 squares around this new larger square
etc.

Then there are 5 ways of doing the first step.
For each remaining step start at the lowest square and work counter clockwise. The first square to be coloured can be done in one of four ways, the highest rightmost (diagonal square) can be coloured in one of four ways all remaining squares can be coloured in one of three ways.

So by my reconing there are $5*3^1*4^2*3^3*4^2*3^5*4^2*3^7*4^2*3^9*4^2*3^{11}*4 ^2*3^{13}*4^2=3^{49}4^{14}5$

Now I might have over counted because the board can be rotated through 90, 180 or 270 degrees and you may or may not want to cound boards with rotational symetry as being identical.