Answer: $2n+1$ if $n$ is odd, $2n-2$ if $n$ is even. Solution: The first two conditions also imply that there can be no $2 \times 2$ checkerboards, so the boundary between black squares and white squares is either a lattice path or cycle (if one color encloses the other). Therefore, the set of squares of each color is the interior of a lattice polygon of genus 0 or 1. (In the latter case, the genus-1 color uses all squares on the outer boundary, and the opposite color must be genus-0.) The third condition requires that the perimeter of each color passes through all $(n-1)^{2}$ interior lattice points, or else there will be a monochromatic $2 \times 2$ subgrid. Hence, by Pick's Theorem, the area of one color is at least $(n-1)^{2} / 2-1=\left(n^{2}-2n-1\right) / 2$, and the difference is at most $n^{2}-\left(n^{2}-2n-1\right)=2n+1$. For even $n$, the number of interior lattice points is odd so there is no cycle that only uses them. (In particular, this means that both colors are genus-0.) It is impossible for the perimeter to only go through one boundary point either, so we need to add at least three more boundary points, which means that we lose $2(3 / 2)=3$ from the bound for odd $n$. Here is one possible set of constructions. Throughout, we'll label the squares as $(x, y)$, for $1 \leq x, y \leq n$: - For $n=2$, we color $(2,2)$ black and the others white. - For odd values of $n$, we create a comb shape using black squares. Specifically, the base of the comb will consist of the squares $(i, 2)$, for $i=2,3, \ldots, n-1$. The teeth of the comb will be $(2k, j)$, for $k=1,2, \ldots, \frac{n-1}{2}$, and $j=3,4, \ldots, n-1$. - For even values of $n>2$, we make a modified comb shape. The base of the comb will be $(i, 2)$ for $i=2,3, \ldots, n$, and the teeth will be $(2k, j)$ for $k=1,2, \ldots, \frac{n}{2}-1$ and $j=3,4, \ldots, n-1$. Furthermore, we add the square $(n, 3)$, and the squares $(n-1,2k+3)$ for $k=1,2, \ldots, \frac{n}{2}-2$.