2
$\begingroup$

The questions says, how many ways are there to color a 3 by 3 board with colors red and blue, so that there are no 2 by 2 red squares.

Since I'm required to solve the problem using inclusion-exclusion principle only, I started by making a 3 x 3 board and analyzing how many 2 x 2 boards can it consist of,

+---+---+---+  +---+---+---+
| 0 | 0 |   |  |   | 1 | 1 |
+---+---+---+  +---+---+---+
| 0 | 0 |   |  |   | 1 | 1 |
+---+---+---+  +---+---+---+
|   |   |   |  |   |   |   |
+---+---+---+  +---+---+---+

+---+---+---+  +---+---+---+
|   |   |   |  |   |   |   |
+---+---+---+  +---+---+---+
| 2 | 2 |   |  |   | 3 | 3 |
+---+---+---+  +---+---+---+
| 2 | 2 |   |  |   | 3 | 3 |
+---+---+---+  +---+---+---+

I assumed that only 4 of the 2 x 2 boxes can be possibly made. There's 4 possible conditions which could lead to a 2 x 2 box with only red color. So, I make the 4 conditions

$C_1 = C_2 = C_3 = C_4$ = 2 x 2 box has red color

N($\bar{C_1}\bar{C_2}\bar{C_3}\bar{C_4}) = S_0 - S_1 + S_2 - S_3 + S_4$

Where $S_0$ is all the possible ways to fill a 3 x 3 board with 2 colors.

$S_1=N(C_1) + N(C_2) + N(C_3) + N(C_4)$

$S_2=N(C_1C_2) + N(C_1C_3) + N(C_1C_4) + N(C_2C_3) + N(C_2C_4) + N(C_3C_4)$

and so on according to the notation of generalization of inclusion exclusion principle. $\bar{N} = N(\bar{C_1}\bar{C_2}...\bar{C_t}) = N - \sum_{(1≤i≤t)}N(C_i) + \sum_{(1≤i<j≤t)}N(C_iC_jC_k) + ...$

=> $S_0 = 2^9$

Because there's 4 possible choices and 2 colors to pick from, using the pigeon hole principle

=> $S_1$ = $4 \choose 1$ $4 + 2 - 1 \choose 2$

=> $S_2$ = $4 \choose 2$$3 + 1 - 1 \choose 1$

=> $S_3 = S_4 = 0$

I wanted to know if I'm on the right path

$\endgroup$
  • $\begingroup$ I get $2^9-4\cdot2^5+(4\cdot2^5+2\cdot2^2)-4\cdot2+1=417.$ $\endgroup$ – bof Jan 16 '17 at 7:48
  • $\begingroup$ What is $S_4$ supposed to be and why do you think it's zero? $\endgroup$ – bof Jan 16 '17 at 7:53
  • $\begingroup$ How do you get $N(C_1)=\binom52=10$? I get $N(C_1)=2^5=32$ because there are $4$ squares that have to be red and $5$ squares that can be red or blue. $\endgroup$ – bof Jan 16 '17 at 8:14
  • $\begingroup$ So $S_4=N(C_1C_2C_3C_4)$ is the number of colorings such that all four of the $2$ by $2$ squares are colored red? And $S_4=0$ because there's NO WAY TO DO THAT??? Er, what happens if I just COLOR EVERYTHING RED??? $\endgroup$ – bof Jan 16 '17 at 8:19
  • 1
    $\begingroup$ If you've got $5$ things to paint, and $2$ colors of paint you can use, the number of ways you can paint them (assuming each of the five things is to be painted in one solid color) is $2\times2\times2\times2\times2$, NOT $\binom52.$ $\endgroup$ – bof Jan 16 '17 at 8:22
2
$\begingroup$

To carry on from where you seem to have left the track a bit:

$S_1=N(C_1) + N(C_2) + N(C_3) + N(C_4)$

$S_2=N(C_1C_2) + N(C_1C_3) + N(C_1C_4) + N(C_2C_3) + N(C_2C_4) + N(C_3C_4)$

$S_3=N(C_1C_2C_3) + N(C_1C_2C_4) + N(C_1C_3C_4) + N(C_2C_3C_4) $

$S_4=N(C_1C_2C_3C_4) $

$N(C_i)$ involves colouring the requisite block red and then free choices for the other five squares, giving $N(C_i) = 2^5$ options and thus $S_1 = 4\cdot 2^5 = 128$

There are two varieties when looking at the components of $S_2$: adjacent and diagonal blocks. These give respectively $3$ and $2$ free squares and there are four adjacent and two diagonal cases, giving $S_2=4\cdot 2^3+2\cdot 2^2 = 32 + 8 = 40$

The components of $S_3$ only have one free square each, so $S_3=4\cdot 2 = 8$

Finally there is only one way to colour every square red as required to make all four blocks red.

Then as you observe, $S_0=2^9$ and the inclusion-exclusion calculation gives:

$R = 512-128+40-8+1 = 417$ cases where there is no red $2\times 2$ block


Cross-checking by a different method; we will have no red block if the centre square is blue, so that is $A_1=2^8=256$ possibilities immediately.

Then if the centre square is red, we can avoid red blocks if opposite mid-side squares are blue. There's a little inclusion-exclusion exercise to get that $A_2=2\cdot 2^6-2^4 = 112$

Then with one mid-side square blue but the opposite red, we can avoid red blocks either by having an adjacent mid-side and the remaining corner blue or having the opposite corners blue. This works out to $A_3 = 4\cdot2^3+4\cdot2^2 = 48$

Finally if everything else is red and the four corners are blue the red blocks are also defeated, $A_4=1$.

Giving $R = 256+112+48+1 = 417$ again.

$\endgroup$

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.