Say I have an N by N grid of white squares. I want to change as many as I can to black, but no black squares can touch each other vertically or horizontally. It's pretty clear that the checkerboard pattern provides the best configuration. But how do you rigorously prove this?
Also, the checkerboard is a simple example, but I'm interested in the general problem of coloring as many black squares as possible, with additional constraints on their arrangements. What are some keywords I should search for regarding this topic? I'm just interested in squares on a grid, not spheres (Kepler problem).
For your specific question: Observe that in any path of adjacent squares of even length, at most half of them can be black.
Then in any $n\times m$ rectangle with an even dimension, you can split it into rows or columns of even length, which puts an upper bound of $nm/2$ on the number of black squares. (Alternatively, you can find a path which goes through all squares exactly once.)
If $n$ and $m$ are both odd, you can split the rectangle into the first column (which can have at most $(n+1)/2$black squares) and the remaining $n\times(m-1)$ rectangle, for which we can apply the previous argument.
In either case, adding the upper bounds for each path gives a total upper bound exactly matching our lower bound from the checkerboard coloring.