7

Suppose I had a $4\times4$ grid. Each square can be colored white, black, or gray. If a grid is colored at random, what is the probability that there is at least one $2\times2$ square of just black squares?

Here's my attempt at a solution:

There are a total of $3^{16}$ possible colorings. There are also 9 $2\times2$ squares in a $4\times4$ grid. Without loss of generality, assume that the top left square is black. Then there are $3^{12}$ ways that the other squares can be colored. Multiplying, we get $9*3^{12}$ possibilities. Thus, we get the probability $\frac{1}{9}$.

This solution seems too easy, and the probability seems a bit too high. Can someone please help?

N. F. Taussig
  • 76,571
Math
  • 425

1 Answers1

1

Your answer is high because you have overcounted the cases where there is more than one square. At the extreme, the case with the whole square black has been counted $9$ times, once for each $2 \times 2$ square. You have the expectation value for the number of $2 \times 2$ black squares.

The normal approach to solve this is the inclusion-exclusion principle. You would note that cases where there is a $2 \times 3$ rectangle have been counted twice, so you should subtract them once. There are $6$ such rectangles and $3^{10}$ ways to color the other squares, so there are $6 \cdot 3^{10}$ cases to subtract. Now a $2 \times 4$ rectangle will have three squares inside it, so was counted three times in the first go and has been subtracted twice, so all is well. The eight square shape that is a $3 \times 3$ square missing a corner has three $2 \times 2$ squares in it and there are $16$ of them, so ....

Ross Millikan
  • 374,822