Black-White Grid coluring without cycles

Question

(I am assuming this is a known question but can't find the right terminology)

Given a $N\times{}N$ grid, colour some of the squares black so that there are no cycles in the "graph". For example, this is a valid 3x3 coloring

@@@
@
@@@ 

and this is not:

@@@
@@
@

What is the largest (most black squares) for $N\times{}N$? It is clearly 3 for 2x2 and 7 for 3x3, but a general formula is not apparent. Even a good algorithm is not obvious.

Here is how to get 72 for 10x10:

@ @@@@@@@@
@@ @ @ @ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @@@ @ @@
@@ @ @@@ @
@ @ @ @ @ 
@@@@@@@@@@

Which shows why this might be tricky, since I could not find (yet) a way to turn this into a regular construction.

Thanks, Joseph

Answer 1

There is an upper bound of $\left\lfloor\frac23(N^2+N-1)\right\rfloor$ which is tight for certain values of $N$.

If there are $B$ black squares, they have $4B$ sides. Of these, we subtract the ones that are along the sides of the grid: there are at most $4N-1$ of these (not $4N$ because then we'd get a cycle around the grid's boundary). Because there are no cycles, there are at most $2(B-1)$ places where two black squares are adjacent (this is the number of edges in a tree).

So the remaining $\ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ sides correspond to boundaries between a black square and a white square.

On the other hand, there are at most $4(N^2-B)-1$ such boundaries, because each one meets one side of a white square (and at least one white square touches the side of the grid). So we have $$ 2B - 4N + 3 \le 4(N^2-B) - 1 $$ which we can solve to get $B \le \frac23(N^2+N-1)$.

---

I can match this upper bound when $N \equiv 4 \pmod 6$ (in which case the bound with the floor included is $\frac23(N^2+N-2)$). In that case, the $10 \times 10$ construction generalizes to repeating the following blocks of height $6$:

@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @

except removing the first row of the top block and the last row of the bottom block. (The pattern can be extended horizontally to any even length, including $N$.)

We could of course count the black squares manually, but the fact that this construction has $\frac23(N^2+N-2)$ black squares also follows by going through the proof above: this construction will have $2(B-2)$ black-square to black-square boundaries, since there are $2$ connected components, and of the $4N$ sides of the grid, all but $2$ border black squares. This lets us solve for $B$.