The Minimum Number Of KingsDiscrete Mathematics Level 5
A certain number of kings are placed on a \(2014 \times 2014\) chessboard. A cell on a chessboard is called occupied if a king is placed on it. A cell is called vulnerable if it shares an edge with an occupied cell. Let \(N\) be the minimum number of kings that must be placed on the chessboard to make sure all cells in the chessboard are vulnerable. Find the last three digits of \(N.\)
Details and assumptions
- In other words, there should exist no configuration with smaller than \(N\) kings which makes all cells vulnerable. But, \(N\) kings can be placed in such a way that all cells are vulnerable.
- A cell that is occupied need not be vulnerable.
- This problem is not original.