# Painting chess board

The task is to paint each of the $64$ squares on a chess board either blue or red. I need to find the number of distinct ways this can be done given that any $2\times 2$ square on the board has two red and two blue squares.

I've tried solving it for a $4\times 4$ board, but I am getting no where. Would appreciate any help

• "2X2 square on the board....." line means if a board have 4 square then 2 will blue and 2 will red .Am i right? – iostream007 May 13 '13 at 10:57
• In the 8x8 chess board (64 squares) if you choose any 2x2 square (there are 7*7 = 49 ways of doing that), it will definitely contain two blue and two red – Quark May 13 '13 at 11:05
• @user14111 That is the correct answer, but how did you do that? – Quark May 13 '13 at 11:28
• @Quark How do you know it is the correct answer? – Řídící May 13 '13 at 11:41
• @Gugg Okay I'm not really sure, but the answer for a chess board was given as 510, which is satisfied by his answer – Quark May 13 '13 at 11:43

For an $m\times n$ chessboard there are $2^m+2^n-2$ ways.

Case I. There are two horizontally adjacent squares of the same color: $2^m-2$ ways.

Case II. There are two vertically adjacent squares of the same color: $2^n-2$ ways.

Case III. None of the above: $2$ ways.

Hint for Case I: There are $2^m-2$ ways to color one row so that two adjacent squares have the same color. The rest of the coloring is determined from that; colors must alternate in each column. (Note, therefore, that Cases I and II do not overlap.)

• Thanks for your help! I did not realize the fact that case 1 and case 2 could not overlap and gave up to the apparent complexity of the problem – Quark May 13 '13 at 12:28

I'll just give some hints that will allow you to easily deduce the formula that user14111 gave in a comment. Call any pair of adjacent squares a domino, which can be horizontal or vertical. Call two dominos neighbours if their union is a $2\times2$ square. Call a domino monochromatic for a colouring if its squares have the same colour.

• If a colouring has some monochromatic domino, then so is any neighbour of it (and it has the opposite colour).
• If there is any monochromatic hoizontal domino, then there is one in each row (in the same pair of columns)
• If there is any monochromatic vertical domino, then there is one in each column (in the same pair of rows).
• Both these conditions cannot be met simultaneously.
• Therefore it suffices to count the following cases, and add up the results:
1. There is at least one monochromatic horizontal domino
2. There is at least one monochromatic vertical domino
3. There are no monochromatic dominoes.
• A solution for case 1. is completely determined by the colouring of its first row, a solution for case 2. is completely determined by the colouring of its first column, and a solution for case 3. is completely determined by the colouring of its top-left corner square.
• Thank you! The final set of hints made it much easier :) – Quark May 13 '13 at 12:29

Observe that if the first row is coloured so that there exist two consecutive squares with the same color, then there is exactly 1 way to color the rest of the board giving $2^m-2$ colouring. If the first row is coloured alternatively starting with blue or with red, then the second row has those 2 possibilities as well and so does the third row and so on giving another $2^n$ colourings. In total $2^n+2^m-2$ colouring for $m\times n$ chess board

Take any square anywhere on the board. It will be part of a 2×2 square. Now only possibilities are

BB.
RR.

or

BR.
BR

or

RB
BR

Note that an alternating pattern (RB) ,i.e, RB is created either in only x axis or only y axis or both. Hence in first case in every two adjacent columns there will be atleast an

R
B

or

B
R

So there is no possibility of two vertical adjacent squares to be of same color. Same kind of argument for case 2

Hence presence of just one unidirectional would create a y-axis or x-axis alternating pattern. So, in each case we just need to decide what colour to start with( I mean the squares of first row or column) and there must be at least one repeatition so that only in one direction alternating pattern occurs.

So, 2^8 -2 for x axis 2^8 -2 for y axis And 2 for all 2×2 squares to be bidirectional,i.e, no unidirectional square or repeatition of colours.

• mathjax references to help you in typesetting. – Siong Thye Goh Mar 2 '18 at 4:02
• Thanks a lot. It is really needed – Neelkamal Bhuyan Mar 2 '18 at 4:15