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

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.

• You are on to something! I can delete the first square, but not the third as that would leave the second square not adjacent to a marked square. But I can delete the fourth square. – Jens Apr 27 '16 at 4:31
• The paper cited above would apply to the problem if we didn't require the marked squares to be adjacent to another marked square. – jwsiegel Apr 27 '16 at 4:41
• Aren't all squares self adjacent? So aren't marked squares vacuously adjacent to a marked square? – Juan Sebastian Lozano Apr 27 '16 at 4:46
• @ Juan Sebastian Lozano - The definition of "adjacent" only refers to "two different squares". – Jens Apr 27 '16 at 4:49
• Oh, I see. That makes this problem harder, then. – Juan Sebastian Lozano Apr 27 '16 at 4:50

## 4 Answers

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

• Does this work on an arbitrary finite board? I tried it on a $4n+1 \times 4n+1$ board and it didn't work, but maybe I tried it wrong. – Juan Sebastian Lozano Apr 27 '16 at 5:52
• I think any finite board will require some extra marked square around the boundary. It'll be O(n) additional squares, though. I'd be interested to know if there is a nice closed form expression for $N$. – jwsiegel Apr 27 '16 at 6:25
• I think there should be one for each case mod 4 (just like my answer below), but I don't know about generally. – Juan Sebastian Lozano Apr 27 '16 at 6:42
• Interesting! The question wasn't looking for an asymptotic result though, and I'm troubled by the fact that none of the boards marked using your marking scheme actually work, except for $n = 2$. How can you take a marking scheme which doesn't work for all $n$ and find a legitimate limit? – Jens Apr 27 '16 at 17:02
• @Jens The problem portion of the board with this layout is the border, which consists of $4(n-1)$ squares. When $n$ is large, this number of squares is tiny relative to the total of $n^2$ squares. That's why, in the limit, you obtain the optimal result that one can cover the board by marking at most "just over" a quarter of the squares. – Dustan Levenstein Apr 27 '16 at 19:49

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.

• Thank you for your explanation! I get it now. I have upvoted your answer and given jwsiegel the "accepted answer" nod. – Jens May 1 '16 at 23:26
• Glad to have helped! :) – Dustan Levenstein May 2 '16 at 0:51

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.

• Nice! I'm trying to test if your numbers work but I'm having a little difficulty because you seem to have overlooked that $n$ must be even. Could you tell me what $N$ you get for $n = 10$? I can't find a solution less than 36. I think the equation of yours I should use here is the one with $(3n + 1)$ in it, giving 34. Correct? – Jens Apr 27 '16 at 17:32
• That is true, I used general $n$. I fixed my bound on that case, it was incorrect because I made a wrong assumption about how I could divide up the last row. – Juan Sebastian Lozano Apr 27 '16 at 19:04
• Thanks! Would you mind spelling out the final answer (which I think you have found) so even I can immediately understand it? I.e. "Given n (a positive even integer), the smallest possible value of N divides into 3 cases as follows: (1) n mod 3 = 0; blah, blah (2) n mod 3 = 1; blah, blah (3) n mod 3 = 2: blah, blah ". If you post it as new Answer I will immediately upvote it (as I did your answer above). Thanks! – Jens Apr 27 '16 at 20:40
• To downvoters: notice that these are upper bounds, I'm not claiming these are the best bounds. The best bound has already been produced, actually, and I would accept that answer instead. – Juan Sebastian Lozano May 1 '16 at 10:08
• Fair enough. It seems I'm not allowed to remove my downvote unless you edit this post, for some reason. If I had the option, I would remove this downvote, but not the one on your other answer, because there you do claim this value of $N$ is optimal. – Dustan Levenstein May 1 '16 at 20:19

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