probability of coloring a $3\times 3$ table with two colors such that no $2\times 2$ square exists

Question

imagine we have a $3\times3$ table ( or $3\times3$ square ) and we want to color each place of that $9$ places with two colors ( red and blue ). find the probability that no $2\times2$ square exists after coloring places .

Answer 1

There are $2^9$ ways to color the square. We now want to count how many ways there are to make a $2\times 2$ square of the same color.

Pick any $2\times 2$ square. There are $2^5$ ways to color the squares not inside the square we chose. The square we chose can be colored in two ways, so we get $2^6$ colors that result in this square being all the same color. There are 4 different $2\times 2$ squares in the $3\times 3$ square, giving us $2^8$.

This double counts some of the boards, for example, if the bottom and middle rows are all blue. Thus we need to exclude the double countings that occur due to $3\times 2$ solid color boards. There are $4\cdot 2^3=2^5$ of these.

The above paragraph also double counts something! Here, we removed the $3\times 3$ solid color board multiple times! We need to add back in the $2$ ways to color the entire board, giving us our final answer of $2^8-2^5+2$. Giving us $$p=\frac{2^8-2^5+2}{2^9}$$This process is called the Inclusion/Exclusion principle.