9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "2X2 square on the board....." line means if a board have 4 square then 2 will blue and 2 will red .Am i right? $\endgroup$ – iostream007 May 13 '13 at 10:57
  • $\begingroup$ 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 $\endgroup$ – Quark May 13 '13 at 11:05
  • $\begingroup$ @user14111 That is the correct answer, but how did you do that? $\endgroup$ – Quark May 13 '13 at 11:28
  • $\begingroup$ @Quark How do you know it is the correct answer? $\endgroup$ – Řídící May 13 '13 at 11:41
  • 1
    $\begingroup$ @Gugg Okay I'm not really sure, but the answer for a chess board was given as 510, which is satisfied by his answer $\endgroup$ – Quark May 13 '13 at 11:43
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Quark May 13 '13 at 12:28
4
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! The final set of hints made it much easier :) $\endgroup$ – Quark May 13 '13 at 12:29
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ mathjax references to help you in typesetting. $\endgroup$ – Siong Thye Goh Mar 2 '18 at 4:02
  • $\begingroup$ Thanks a lot. It is really needed $\endgroup$ – Neelkamal Bhuyan Mar 2 '18 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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