The answer is $n^2+n+1$. Proof that $n^2+n$ can fail: I divide the board into $n^2$ 2x2 squares. For squares above the main diagonal of 2x2 squares, paint the upper right square black and for squares below the main diagonal only paint the lower left square black. Proof that $k\ge n^2+n+1$ works: if I can somehow get the number of black cells to increase, I clearly win. The objective is to get two black cells to share an edge. We will prove a lemma. Lemma wrote: Suppose $k > \frac{(m+1)(n-1)}{4}$ squares on an $m\times n$ square are painted black. Then I can get two squares to be adjacent. We perform two smoothing operations. In what follows, b's denote black squares and w's denote white squares If I have wb bw I turn it into bw wb And furthermore if I have wbw wwb bww I turn it into wwb bww wbw Now consider a diagonal of b's, say squares $b_1,\cdots,b_t (t\ge 1)$ are black and $b_t$ is one square below and to the right of $b_{t-1}$, and none of $b_1,\cdots,b_t$ are on the leftmost column or the bottom row. We can setup the coordinates for the grids such that if $b_1 = (x,y)$, then $b_j = (x+j-1, y+j-1)$. Assign $(x-1,y), (x,y+1), (x-1,y+1)$ to $b_1$ (note down is positive), and $(x+j-1,y+j), (x+j-2,y+j), (x+j-3,y+j)$ to $b_j$ for $j=2,\cdots,t$. It is clear that by our smoothing operations, the squares assigned to each $b_j$ must be white. Furthermore, each white square is assigned at most once (can be checked by casework) Let $a$ be the number of black cells that are not on the leftmost row or bottom column. If $a\le \frac{(m-1)(n-1)}{4}$, then it is easy to see that there are at most $\frac{m+n}{2}$ cells on the leftmost row or bottom column, so the total number of black cells is at most $\frac{mn + m + n +1}{4}$. Otherwise, $a > \frac{(m-1)(n-1)}{4}$. Let $c = a - \frac{(m-1)(n-1)}{4}$ So black squares must have assigned squares on the leftmost column or bottom row. Suppose the assigned squares divide the leftmost column and bottom row into "blocks" $s_1,\cdots,s_t$. Then $|s_1|+\cdots+|s_t| \le m+n-1-4c$. Let $|s_1|+\cdots+|s_t| = m+n-1-d$. The number of black squares on the leftmost column and bottom row is at most $$\sum_{j=1}^t \frac{|s_j|+1}{2} \le \frac{m+n-1-d+t}{2}$$ If there are more than $\frac{(m+1)(n+1)}{4}$ black squares, this is greater than $\frac{m+n-2c}{2}$. This implies that $t> d+1-2c$, so there are more than $d-2c$ "separators" from assigned squares. Observe that $d\ge 4c$ and if $s$ is the number of separators, $m+n-1-d = |s_1|+\cdots+|s_t| \le m+n-1-2s < m+n-1-2(d-2c) $. When $d\ge 4c$, this cannot happen, which is a contradiction. Therefore, in total the number of squares is at most $\frac{(m+1)(n+1)}{4}$, or I can get two black squares to be adjacent. Call two adjacent (share an edge) black squares a domino. Now we deliver the final blow: Final Blow wrote: Let $m,n\ge 3$ be positive integers. If I can set $k$ squares to be black so that the number of black squares never increase, then $k\le \frac{(m+1)(n+1)}{4}$ We induct on $m+n$. The case where $\min\{m,n\}=3$ is easy. Henceforth assume $\min\{m,n\}\ge 4$ Let $f(m,n)$ denote the maximum number of initial black squares so that the number of black squares never increases. It is easy to show that $f(1,n)=f(2,n)=n$. We now begin our inductive step. WLOG the "domino" is vertical, on rows $r,r+1$. WLOG, $r \le m+1-r$ by symmetry. If $r\le 2$ we can apply inductive hypothesis on $(m-1,n)$ on rows 2 to $m$ because row 1 has at most $1 < \frac{n+1}{4}$ black square. If row 1 has two black squares then I can move the "domino" right, create a "domino" on rows 1 and 2 and make the number of black squares increase. (*) If $r= 3$ we note that row 1 has at most $\frac{2(n+1)}{4}=\frac{n+1}{2}$ squares since there cannot be two adjacent black squares on row 1, or I can move them down and also move the two vertically adjacent black squares right to make the number of black squares increase. This implies that row 1 and row 2 in total can have at most $\frac{n+1}{2}$ squares, because if row 2 has a square, we can do (*) to see that it has at most one square and row 1 also has at most one square. Since $r\le m+1-r$, $m\ge 5$. Applying inductive hypothesis on $(m-2,n)$ yields that there exists at most $\frac{(m-1)(n+1)}{4}$ squares on rows $3$ to $m$, so we are done with $r=3$. Suppose $r\ge 4$. Note if $r>4$ and we cannot move the domino up to rows $4,5$, let $s$ be the maximal number $<r$ such that row $s$ has no block cells. If $s\le 3$ we are back to the $r\le 2$ or $r=3$ case, so assume $s\ge 4$, then we can apply inductive hypothesis on $(s-1,n)$ on the first $s-1$ rows, and on $(m-s, n)$ on rows $s+1,\cdots,m$ (note $m-s \ge m-r \ge r-1\ge s-1$) Henceforth assume $r=4$ and row 3 has no black cells, because otherwise I can use (*) to go back to the $r=3$ case. We can see the first two rows have at most $n$ cells, which means the first 4 rows have at most $n+1$ cells. Applying i.h. on rows $5$ to $m$ finishes.