A Graph-Theory Related Question

Question

Let $n$ be a positive integer and partition a grid of $4n$ by $4n$ unit squares into $4n^2$ squares of sidelength $2$. (The squares with sidelength $2$ have all of their sides on the gridlines of the $4n$ by $4n$ grid.) What's the minimum number of unit squares that can be shaded such that every square of sidelength $2$ has at least one shaded square, and there exists a path between any two shaded squares going from shaded squares to adjacent shaded squares? (Two squares are adjacent of they share a side.)

I think the answer is $6n^2-2$. I got it by partitioning the $4n$ by $4n$ unit squares into $n^2$ squares of sidelength $4$, shading in the four center unit squares of each sidelength $4$ square (so that every square with sidelength $2$ has at least one shaded square), and connecting the shaded squares to another. There are $4n^2$ center unit squares, and a connection between any two groups of center squares requires two squares. There are $n^2$ groups of center squares, so for the shaded squares to be connected, we need at least $n^2-1$ connections. (Similar to how a connected graph on $n$ vertices needs at least $n-1$ edges.) Each connection is two squares, so we need to shade an additional $2(n^2-1)$ squares. Adding this to $4n^2$ gives $6n^2-2$.

This is by no means a proof. There are of course valid configurations in which some square with sidelength $4$ does not have the center $4$ squares shaded in. Could someone help me prove that $6n^2-2$ is the minimum? Thanks.

Answer 1

Let $p$ be a path consisting of $m$ shaded unit squares (where every two adjacent shaded squares share a side). Define a binary string $B_p=b_0b_1b_2\dots b_m$, where $b_0b_1=10$ and for $i>1$, $b_i=1$ iff the $i$th square in $p$ belongs to a previously unseen 2x2 square. Clearly, the number of ones in $B_p$ equals the number of 2x2 squares visited by $p$.

It can be shown that every substring of length 6 of $B_p$ contains at most 4 ones. Furthermore, the maximum number of ones in $B_p$ is:

• if $m\equiv 0\pmod{6}$, then $\frac{4m+6}6$ ones
• if $m\equiv 1\pmod{6}$, then $\frac{4m+2}6$ ones
• if $m\equiv 2\pmod{6}$, then $\frac{4m+4}6$ ones
• if $m\equiv 3\pmod{6}$, then $\frac{4m+6}6$ ones
• if $m\equiv 4\pmod{6}$, then $\frac{4m+8}6$ ones
• if $m\equiv 5\pmod{6}$, then $\frac{4m+4}6$ ones

To visit $4n^2$ 2x2 squares, path $p$ must contain $m\geq \frac{6\cdot 4n^2 - 8}{4}=6n^2-2$ shaded squares.

It remains to consider a case when the shaded squares form not a path but a tree, which I believe can be done similarly.