This problem is from AIME 2001.

PIE will kill immediately.

biomathematics wrote: This problem is from AIME 2001. can u pls send the link?

I'm getting 418. Can anybody confirm?

We divide situations by the color of the center mass, blue or red. $(1)$ When the color of the center mass is blue. This time, how other $8$ masses are colored, there are no $2*2$ red mass. Thus, the the number of coloring is $2^8=$256 $(2)$ When the color of the center mass is red. This time, it is not so simple. We divide into some cases by the number of red mass other than the center.($=$ set $x$) $(2)-a$ When $x=0$ This time is OK, so, the number of coloring is 1. $(2)-b$ When $x=1$ This time, every $8$ mass is OK, so, the number of coloring is 8 $(2)-c$ When $x=2$ This time, every $8$ mass is OK, so, the number of coloring is $_8 \mathrm{C} _2=$28 $(2)-d$ When $x=3$ This time, we put $3$ red mass so as not to make one $2*2$ red mass, so, the number of coloring is $_8 \mathrm{C} _3-4=$52 $(2)-e$ When $x=4$ This time, we put $4$ red mass so as not to make one $2*2$ red mass, so, the number of coloring is $_8 \mathrm{C} _4-(4*5)=$50 $(2)-f$ When $x=5$ This time, we put $5$ red mass so as not to make one or two $2*2$ red mass, so, the number of coloring is $_8 \mathrm{C} _5-(4*(_5 \mathrm{C} _2-2)+4)=$20 $(2)-g$ When $x=6$ This time, we must put $6$ red mass in the shape like $H$, so, the number of coloring is 2 We take sum of the underlined number, and get the answer. The answer is $256+1+8+28+52+50+20+2=\boxed{417}$ Done!

Lets simplify the problem. First we are going to find the number of ways we can paint the $3x3$ board without any restriction. Its clearly $2^9$. Now, the number of ways to place a $2x2$ red squared board in the original one are clearly 4. Hence the number of ways to paint the rest $5$ squares are $2^5$. from the above, we get that the number of ways to paint the unit cells such that at least one $2x2$ cell is collored red are $4*2^5=2^7$. Yet we have counted twice each $2x3$ red square. The number of ways similarly to paint the board such that at least one $3x2$ Rectangle is red are $4x2^3=2^5$. But yet we must add the $3x3$ so the total number of ways are: $2^9-2^7+2^5+1=417$ (Note: That's the PIE method)

bartle-doo wrote: PIE will kill immediately. What is PIE???

Akatsuki1010 wrote: bartle-doo wrote: PIE will kill immediately. What is PIE??? Principle of Inclusion and Exclusion