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 .
Asked
Active
Viewed 95 times
1
-
Do you want to know if it is possible to do, or do you want to know if you color each square at random with probability $\frac{1}{2}$ what the probability of such an occurrence is? – Stella Biderman Jan 01 '16 at 18:02
-
i know it is possible . i want to know the probability of it ... excuse me for the wrong title ! @StellaBiderman – Arman Malekzadeh Jan 01 '16 at 18:08
1 Answers
0
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.
Stella Biderman
- 31,155