4. In chess, a knight placed on a chess board can move by jumping to an adjacent square in one direction (up, down, left, or right) then jumping to the next two squares in a perpendicular direction. We then say that a square in a chess board can be attacked by a knight if the knight can end up on that square after such a move. Thus, depending on where a knight is placed, it can attack as many as eight squares, or maybe even less.
In a $10 \times 10$ chess board, what is the maximum number of knights that can be placed such that each square on the board can be attacked by at most one knight?
Solution. The answer is 16 . 16 knights can be placed as follows, where a blue square represents a square with a knight:
We will now show it is not possible to place more than 16 knights. First we color the grid black and white in checkerboard fashion:
Note that each knight on a black square can only attack white squares, and each knight on a white square can only attack black squares. If there are more than 16 knights on the grid, there must be at least 9 knights on white squares or at least 9 knights on black squares. Without loss of generality, let there be at least 9 knights on black squares. Let us split the $10 \times 10$ grid into four $5 \times 5$ grids. Note that two of those four have more black squares than white squares (we call this $A$ ), and the other two have more white squares than black squares (we call this $B$ ).
We see that in grids of type $A$, we can only place at most 3 knights on black squares (center and two opposite corners), and in grids of type $B$, we can only place at most 2 knights on black squares (2 squares horizontal and 2 squares vertical from one another). Since there are at least 9 knights on four $5 \times 5$ grids, at least one of those grids has at least 3 knights (which must be type $A$ ). Assume that the $A$ grid on the bottom left corner has 3 knights on black squares. Then we will have two cases (red squares indicate black squares which we cannot place a knight on):