Minimum number of marked squares on $n × n$ board

Question

Came across this question:

Consider an $n × n$ square board, where $n$ is a fixed even positive integer. The board is divided into $n^2$ unit squares. We say that two different squares on the board are adjacent if they have a common side.

$N$ unit squares on the board are marked in such a way that every square (marked or unmarked) on the board is adjacent to at least one marked square. Determine the smallest possible value of $N$.

I've found an upper bound of $N = \frac {n^2}2$. But is this the smallest possible value of $N$? If so, how can I prove it?

I've included an illustration of my upper bound for $n=2$ and $n=4$ below.

Edit

@jwsiegel has linked to the supposed solution here: http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln993.html

It gives the solution $$N = \frac{n(n+2)}{4}$$ I don't understand how this solution is correct. The instructions for marking squares is given as:

1. Color alternate squares black and white (like a chess board).
2. Look first at the odd-length white diagonals. In every other such diagonal, mark alternate squares (starting from the border each time, so that r+1 squares are marked in a diagonal length 2r+1).

That's it. I have followed these instructions (as I understand them) for $n=4$ and $n=6$ below, using an X to indicate a marked square:

The number of marked squares fits the given solution, i.e. $N = 6$ for $n = 4$ and $N = 12$ for $n = 6$, but NO marked square is adjacent to any other marked square! How then is this a valid solution?

I can only see 3 possibilities:

1. I have marked incorrectly, or
2. The people who made this solution count a common corner as a common side between 2 squares, or
3. The solution is incorrect.

Please explain what I'm missing.

Answer 1

Consider an infinite checkerboard with squares labelled by pairs of integers and mark every square whose indices satisfy $$(i,j) \equiv (0,0) \pmod{4}$$ $$(i,j) \equiv (0,1) \pmod{4}$$ $$(i,j) \equiv (2,2) \pmod{4}$$ $$(i,j) \equiv (2,3) \pmod{4}$$ This provides a marking of the infinite board with the desired property such that every fourth square is marked. Thus we have that $$\lim_{n\rightarrow \infty} \frac{N}{n^2} = \frac{1}{4}$$ which is clearly the best possible asymptotic result.

In fact the value of N is n(n+2)/4. The full solution can be found here. http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln993.html

Answer 2

You can produce upper bounds for the three cases $n \equiv 1,2,3 \mod{3} $.

In a $3n \times 3n$ square the upper bound is $3n^2$ because you can color every third row.

In the case that it is a $(3n+1) \times (3n+1)$ square, then the upper bound is $3n^2+ n + 2*\lceil \frac{(3n + 1)}{4} \rceil$. This results from coloring every third row and adding a pair every two uncolored spaces on the last row.

If it is a $(3n+2) \times (3n+2)$ board, the upper bound is $(3n+2)(n+1)$. This is what results from coloring every third row and the last row.

All of these cases have the asymptotic ratio of colored squares to total squares of $\frac{1}{3}$, but also work on any finite board with a slightly higher ratio.

Answer 3

Given a square of size $n \times n$, where $n \in \mathbb{Z^+} $, the smallest value of shaded squares $N$ can be determined as one of these three cases:

1. If $n \equiv 3k \equiv 0 \mod 3$, then $N = 3k^2$

2. If $n \equiv 3k +1 \equiv 1 \mod 3$, then $N= 3k^2 + k + 2*\lfloor\frac{3k+1}{4}\rfloor$

3. If $n \equiv 3k +2 \equiv 2 \mod 3$, then $N= (3k+2)(k+1)$

Answer 4

jwsiegel has already provided both an asymptotic answer to the original question, and a link to a closed-form solution. I will address the Juan's question in the comments on jwsiegel's answer and Jens's follow-up question in the original post.

In answer to Juan's question, "For even n, this is better, but does this work if n is odd?":

Nothing in jwsiegel's asymptotic result makes any assumption on the parity of $n$. His answer provides a covering of the infinite plane which satisfies the rules given in the original post. When this marking is restricted to an $n \times n$ board, you get a marking of the board in which every interior square is adjacent to a marked board, with roughly a forth of the squares marked (exactly 1/4 if $n$ is a multiple of 4). To then cover the boundary as well, you need to add no more than $4(n-1)$ additional squares. When $n$ approaches infinity, this contribution becomes negligible, so we get that, for $n$ large, his covering of the board requires about a quarter of the squares to be marked. Since each square is adjacent to at most 4 other squares, it follows that this result is asymptotically optimal.

It is, in principle, possible to precisely calculate how many squares are marked by this procedure, but there is no reason to expect that it will be optimal for any fixed $n$. What the asymptotic solution does do is provide guidance for what a closed-form solution must satisfy, namely, that $$\lim_{n \to \infty} \frac{N}{n^2} = \frac{1}{4}.$$

Now, for OP's question. You forgot this part: "In every other such diagonal..." With that in mind, here are the cases you wrote up, corrected. Let the upper-left hand corner be white, as in your pictures. I've indicated the black squares using an ascii box; hopefully that should make it pretty clear.

$n=4$:

 X | ■ |   | ■ 
---------------
 ■ |   | ■ | X 
---------------
   | ■ |   | ■ 
---------------
 ■ | X | ■ |   

$n=6$:

 X | ■ |   | ■ | X | ■ 
-----------------------
 ■ |   | ■ |   | ■ |   
-----------------------
   | ■ | X | ■ |   | ■ 
-----------------------
 ■ |   | ■ |   | ■ | X 
-----------------------
 X | ■ |   | ■ |   | ■ 
-----------------------
 ■ |   | ■ | X | ■ |   

Observe that every black square is adjacent to exactly one marked white square. Now, as you observed, of course, no white square is adjacent to any marked square. But if we apply the exact same procedure to mark the black squares, then we obtain a marking of the entire board such that every square is adjacent to exactly one marked square. Then the claims are that (1) this board has $n(n+2)/4$ marked squares, and (2) this number of marked squares is optimal. Note that this closed form solution absolutely does depend on assuming that $n$ is even.