2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$ Apr 4 at 14:18
  • 2
    $\begingroup$ 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$ $\endgroup$
    – Henry
    Apr 4 at 14:35
  • $\begingroup$ 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? $\endgroup$ Apr 4 at 21:17
  • $\begingroup$ @MishaLavrov The first one. $\endgroup$ Apr 5 at 2:16

1 Answer 1

1
$\begingroup$

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.$$

$\endgroup$
2
  • $\begingroup$ Thank you very much. I wonder if any prior research has been done to locate some sane bounds for large $n$s? $\endgroup$ Apr 5 at 2:47
  • 1
    $\begingroup$ @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/… $\endgroup$
    – Jbag1212
    Apr 7 at 22:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .