On a covering of an $N\times N$ chessboard such that each black square is next to a covered square

86 Views Asked by At

Consider an $N\times N$ chessboard where $N$ is an even positive integer. Determine the smallest amount of pawns one must place on the board such that each black square is next to at least one pawn.

After testing some cases for small $N$, I believe the answer to be $\frac{N(N+2)}8$ but I can't prove it. It's quite simple to find a configuration that works for this amount of pawns but I am unable to prove that the bound can't be any lower.

1

There are 1 best solutions below

0
On BEST ANSWER

You can derive a simple lower bound by dividing the total number of black squares by the maximum number of black squares covered by each pawn: $(N^2/2)/4=N^2/8$.

Your conjectured lower bound is better and can be derived by exhibiting a set of $N(N+2)/8$ black squares such that no two can be covered by the same pawn. You can think of this as a packing problem that is dual to your covering problem.