G2.1 On a $3 \times 3$ grid of 9 squares, each squares is to be painted with either Red or Blue. If $\alpha$ is the total number of possible colouring in which no $2 \times 2$ grid consists of only Red squares, determine the value of $\alpha$.
If there is no restriction, number of possible colouring $=2^{9}=512$
(1)If all 9 squares are painted as red, number of colouring $=1$
(2)If there are exactly three $2 \times 2$ grid consists of only Red squares, possible pattern may be:
$90^{\circ}$ rotation gives another possible pattern
Number of colouring $=4$
(3)If there are exactly two $2 \times 2$ grid consists of only Red squares, possible pattern may be:

Number of colouring $=2$
$90^{\circ}$ rotation gives
another possible pattern
Number of colouring
$$
=4 \times 5=20
$$
(5)If there is exactly one $2 \times 2$ grid consists of only Red squares, possible pattern may be:
$90^{\circ}$ rotation gives
another possible pattern
Number of colouring $=4$
$90^{\circ}$ rotation gives
another possible pattern
Number of colouring
$$
=4 \times 5=20
$$
$90^{\circ}$ rotation gives
another possible pattern
Number of colouring
$$
=4 \times 5=20
$$
$90^{\circ}$ rotation gives
another possible pattern
Number of colouring
$$
=4 \times 3=12
$$
$90^{\circ}$ rotation gives
another possible pattern
Number of colouring
$$
=4 \times 3=12
$$
$\therefore$ Total number of possible colouring in which no $2 \times 2$ grid consists of only Red squares
$=$ No restriction - all 9 red squares - exactly $32 \times 2$ red grid - exactly $22 \times 2$ red grid - exactly $12 \times 2$ red grid $=512-1-4-2-20-4-20-20-12-12=417$
Method 2 (a)All 9 blue squares $=1$ pattern. (b) 8 blue squares +1 red squares $=9$ patterns.
(c) $7 \mathrm{~B}+2 \mathrm{R}=C_{2}^{9}=36$ patterns, (d) $6 \mathrm{~B}+3 \mathrm{R}=C_{3}^{9}=84$ patterns, (e) $5 \mathrm{~B}+4 \mathrm{R}=C_{4}^{9}-4=122$ patterns
(f) $4 \mathrm{~B}+5 \mathrm{R}=C_{5}^{9}-4 \times 5=106$ patterns, $(\mathrm{g}) 3 \mathrm{~B}+6 \mathrm{R}=C_{6}^{9}-4 \times C_{2}^{5}+4=48$ patterns
(h) $2 \mathrm{~B}+7 \mathrm{R}=8+2=10$ patterns, (i) $1 \mathrm{~B}+8 \mathrm{R}=1$ pattern

Total number of different patterns $=1+9+36+84+122+106+48+10+1=417$