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.