Fdtxjr

Let's assume we have random pixel generator which has 10X10 resolution (100 pixels in total) and each pixels can have 3 different colors.
I'm trying to calculate probability of having at least one 2X2 same color square block on that screen.

Here is my logic for such calculation:

1) Odds of all pixels having same color in 2X2 square block is 1/27 (3/3^4)

2) Odds of there is at least two different colors in 2X2 square block is 26/27 (1-1/27), which is complement probability of (1)

3) There are 81 different group of 2X2 square blocks on 10X10 grid.

4) Probability of that one 2X2 square block at least having two different colors is
(26/27)^81, based on complement probability.

5) Therefore probability of at least one 2X2 square block having same color is

1-(26/27)^81=95% approximately.

However,

-4 pixels on 10X10 grid which are located at the corners (top left,top
right,bottom left & bottom right) can be only in one 2X2 square block each

-All pixels located in outermost parts except these 4, can be in two different 2X2 square blocks each

-All remaining pixels inside outermost lines can be in four different 2X2 square blocks each.

As I treated all pixels equally I didn't reflect the condition above in my calculation. How can I reflect the condition above in my calculation and have the correct probability? Is this mathematically possible to demonstrate via calculations?

Thanks a lot!

I tend to believe that there is no simple formula for that, but you can use ideas from so-called "dynamic programming with profile" to calculate it.

Let $x$ be the number of 'bad' colorings (with no single-colored $2*2$ squares). Clearly the answer is $$1-fracx3^100$$

Next, let $f(n, mask)$ (where $n in 0 .. 9$ and $mask in 1, 2, 3 ^ 10$, $1, 2, 3$ refers to colors) be the number of ways to paint first $n+1$ rows so that:

1) There is no single-colored $2*2$ square

2) The last row coloring is determined by $mask$

Clearly $$x = sum_mask in 1, 2, 3 ^ 10f(9, mask)$$

We use recurrent formula in order to calculate $f(9, mask)$


Thus, $$f(n, mask) = sum_mask' in 1, 2, 3 ^ 10f(n - 1, mask') * permitted(mask', mask)$$ where $$permitted(mask1, mask2) = begincases
1, & textif $mask2$ painted next to $mask1$ doesn't produce single-colored 2*2 square \
0, & textotherwise endcases$$

and
$$f(0, mask) = 1$$
for any $mask$

The formula above simply reflects the fact that any coloring of the first $n$ rows is proper combination of coloring of first $n - 1$ rows and the last one, and all you need to ensure that the coloring of the last row (defined by $mask$) together with the coloring of previous row (defined by $mask'$) don't form a single-colored square.

If you just need a formula then the job is done. If you actually need to get a number you will have to wait a couple of hours (or even days) waiting your computer to do $10 * 3 ^ 2 *10 approx 3 * 10^10$ operations calculating all these values. It will take a time, but it is not impossible as full brute-force taking $3^100 approx 5 * 10 ^ 47$ which is almost forever.

Upd:


By these formulas the exact number of colorings with no single-colored $2*2$ square is $$34588239301492881803538634375825365877151370240$$ Thus, the probability is $$frac3^100 - 345882393014928818035386343758253658771513702403^100 = 0.9328875670549894$$