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.

  • 6
    $\begingroup$ A less vague title will get you more attention, especially when the question drops off the front page. $\endgroup$ – Brendan McKay Nov 24 '15 at 8:40

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.