# How many ways are there to $2$-Color an $N$ by $N$ Grid such that there is at least one $3$ by $3$ Square?

Given an $$N$$ by $$N$$ grid, how many ways are there to $$2$$-color the grid such that there is at least one $$3$$ by $$3$$ grid with all its four corners having the same color?

Initially I had this expression $$n = 2(N-2)^2\cdot2^{N^2-4}.$$

However, it is clear that this is incorrect because I did not take into account for repetitions.

Thanks in advance for any help.

• @Jbag1212 I'm not sure... If in one count I colored square $A$'s corners in white and then randomly happened to assign square $B$'s corners uniformly to the color black, then in another I could intentionally assign square $B$'s corners black and then happen to give $A$ white monochromatically. Apr 4 at 14:18
• Not checked: For $n=3$, I get $64$. For $n=4$, I get $27120$. For $n=5$, I get $22284432 = 2^4 \times 3^2 \times 154753$ which does not look promising, though this is also $2^{25}-2^4 \times 5^4 \times 7^2\times 23$ Apr 4 at 14:35
• Which of the two options in this picture is meant when we 2-color a grid and see a $3\times 3$ subgrid whose corners have the same color? Apr 4 at 21:17
• @MishaLavrov The first one. Apr 5 at 2:16

Consider $$n \geq 3$$.

Part 1

We first consider the concept of a "3-by-3 square sub-grid." The procedure to produce one of these is to first highlight 4 dots that are corners of a 3-by-3 square. This is the start of our "3-by-3 square sub-grid." Once this is drawn, consider other possible 3-by-3 squares. Some of these 3-by-3 squares will "overlap" and share an edge with the original 3-by-3 square we drew. If so, add any of these corners onto our "3-by-3 square sub-grid." Basically, we are just looking at the subgrids which have a gap of one dot in between them (as opposed to our original grid which has a gap of 0 dots).

Example

For the 5-by-5 grid, there is a "sub-grid" consisting of 9 squares total. If we label each point on the grid $$(a,b)$$ with both $$a, b \in \{1,2,3,4,5\}$$, then there is a subgrid of 9 squares total consisting of $$(a,b)$$ with both $$a$$ and $$b$$ odd. There is also a subgrid consisting of $$(a,b)$$ with $$a$$ even and $$b$$ odd of 6 squares total, a subgrid consisting of $$(a,b)$$ with $$a$$ odd and $$b$$ even of 6 squares total, and a subgrid consisting of $$(a,b)$$ with $$a$$ even and $$b$$ even of 4 squares total.

In General

Consider the two cases: $$n$$ even and $$n$$ odd. If $$n$$ is even then there are 4 subgrids each of size $$(\frac{n}{2})^2.$$ If $$n$$ is odd there are 4 subgrids, one of size $$(\frac{n+1}{2})^2,$$ two of size $$(\frac{n+1}{2})(\frac{n-1}{2}),$$ and one of size $$(\frac{n-1}{2})^2.$$

Note that:

$$n$$ even: $$4(\frac{n}{2})^2 = n^2.$$

$$n$$ odd: $$(\frac{n+1}{2})^2 + 2(\frac{n+1}{2})(\frac{n-1}{2}) + (\frac{n-1}{2})^2= n^2.$$

Each of these subgrids is independent of the other subgrids. In other words, a 3-by-3 square in one subgrid shares no points in common with potential squares in other subgrids. Therefore, finding a 3-by-3 square in the large grid is equivalent to finding a 2-by-2 square in one of the subgrids. So define $$f(m,k)$$ to be equal to the number of ways of to 2-color an $$m$$ by $$k$$ grid such that there is at least one 2-by-2 square. Define $$g(m,k)$$ to be the complement, the number of ways to 2-color an $$m$$ by $$k$$ grid such that there are no 2-by-2 squares. In general, $$f(m,k) + g(m,k) = 2^{m k}.$$ Then the answer to the original question is:

$$n$$ even: $$2^{n^2} - g(\frac{n}{2},\frac{n}{2})^4$$

$$n$$ odd: $$2^{n^2} -g(\frac{n+1}{2},\frac{n+1}{2}) \cdot g(\frac{n+1}{2},\frac{n-1}{2})^2 \cdot g(\frac{n-1}{2},\frac{n-1}{2})$$

Part 2

We have reduced the problem to determining $$f(m,k),$$ where $$f(m,k)$$ is the number of ways to 2-color an $$m$$ by $$k$$ grid such that there is at least one 2-by-2 square all of the same color. Or, equivalently, to determining $$g(m,k).$$ I do not think this will be simple in general, and I give a small example to show why.

Example

For example, for the simple case of $$f(2,k)$$ we can determine that $$f(2,1)=0.$$ We also know that $$f(2,2) = 2.$$ We have $$g(2,1) = 4-0 =4$$ and $$g(2,2) = 16-2=14.$$

Let $${Black \choose Black} = \begin{pmatrix} 1 \\ 0 \\ 0 \\0 \end{pmatrix}, {Black \choose White} = \begin{pmatrix} 0 \\ 1 \\ 0 \\0 \end{pmatrix}, {White \choose Black} = \begin{pmatrix} 0 \\ 0 \\ 1 \\0 \end{pmatrix}, {White \choose White} = \begin{pmatrix} 0 \\ 0 \\ 0 \\1 \end{pmatrix}$$
Now, if we have $${Black \choose Black}$$ we can place next to this anything except $${Black \choose Black}.$$ If we have $${Black \choose White}$$ or $${White \choose Black}$$ we can place anything next to these. If we have $${White \choose White}$$ we can place next to this anything except $${White \choose White}$$. Therefore, $$g(2,k) = \begin{pmatrix} 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}^{k-1} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}$$ $$g(2,k) = \left(\frac{1}{17} \times 2^{-k-1}\left((17-5 \sqrt{17})(3-\sqrt{17})^k+(17+5 \sqrt{17})(3+\sqrt{17})^k\right)\right)$$

You can verify the above formula works for $$k=1,2.$$ Wolfram

We also replicate what @Henry predicted for $$n=4$$: $$2^{16} - (14)^4 = 27120.$$

• Thank you very much. I wonder if any prior research has been done to locate some sane bounds for large $n$s? Apr 5 at 2:47
• @mathy_mathema It is an open question as far as I can tell. I made a little bit of progress and opened up a question here math.stackexchange.com/questions/4895032/… Apr 7 at 22:53