Painting of a block in P&C

Question

Consider a grid as shown in figure having 8 blocks of dimension 1 × 1. Each block is to be painted with either blue or red colour. In how many ways this can be done if at least one block of dimension 2 × 2 is to be painted red completely ?

I am not able to approach this problem. Can this problem be solved by inclusion-exclusion principle.

Answer 1

Define sets $A,B,C$ as follows . . .

• Let $A$ be the set of configurations for which the upper left $2{\times}2$ submatrix is painted red.$\\[4pt]$
• Let $B$ be the set of configurations for which the upper right $2{\times}2$ submatrix is painted red.$\\[4pt]$
• Let $C$ be the set of configurations for which the lower right $2{\times}2$ submatrix is painted red.

The goal is to find $|A\cup B\cup C|$.

Applying the principle of inclusion-exclusion, $$ |A\cup B\cup C| = \Bigl(|A|+|B|+|C|\Bigr) - \Bigl(|A\cap B|+|B\cap C|+|C\cap A|\Bigr) + |A\cap B\cap C| $$ Then we get

• $|A|=|B|=|C|=2^4$ since for each of those three sets, there are exactly $4$ free squares.$\\[4pt]$
• $|A\cap B|=|B\cap C|=2^2$ since for each of those two sets, there are exactly $2$ free squares.$\\[4pt]$
• $|C\cap A|=2$ since for that set, there is exactly $1$ free square.$\\[4pt]$
• $|A\cap B\cap C|=1$ since for that set, there are no free squares.$\\[4pt]$

hence $$ |A\cup B\cup C| = 3{\,\cdot\,}2^4-(2{\,\cdot\,}2^2+2)+1 = 39 $$

Answer 2

Let $w(n)$ be the number of ways in which at least $n$ $2\times 2$ squares are painted red. Now, $$w(1)={3\choose 1} \cdot 2^4 $$ (choose one of the three squares and paint the remaining four either red/blue) $$ w(2)= 2^2+2^2 +2^1$$ (considering the different possibilities of picking $2$ such squares and coloring the remaining one(s) ) $$w(3)=1$$ Then, by inclusion-exclusion, the number of ways where at least one such square is red will be $$w(1)-w(2)+w(3) =\color{purple}{39}$$