Combinatorics – Painting Chess Board

coloringcombinatorics

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

Best Answer

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.