What is the maximum number of cells we can select in a n x m square such that no 2 cells share a side?

Question

Consider a square of having n rows and m columns of cells. What is the maximum number of cells we can select such that no 2 selected cells share a side?

From intuition I can say that the answer should be (nm)/2 rounded up.
I tried proving this by dividing the n x m square into 2 x 1 blocks. Now each block can have a max of 1 selected cell. Total such blocks is (nm)/2 rounded down. So we can select (nm)/2 rounded down cells.
Now one cell will remain if the total (i.e. nm ) is odd, and we can select that square as well. So now we will have (n*m)/2 rounded up selected cells.

My question is - Is the answer (i.e. (n*m)/2 rounded up ) correct . And if it is , then is my proof correct?

Answer 1

The answer is correct, but your proof only shows that $\lceil \frac{nm}{2} \rceil$ is an upper bound and does not establish that this bound can actually be reached. Of course you can easily fix the proof by showing that a checkerboard colouring is a solution that reaches that bound.