What is the maximum number of knights that can be positioned on a $5\times5$ chess board, so that each knight attacks exactly two other knights?
. X X X . X X . X X X . . . X X X . X X . X X X .
To show that xnor's answer with 16 knights is indeed best possible, consider a standard black-and-white chessboard coloring so that the four corner squares, the central square and both diagonals are black. Then there are $13$ black and $12$ white squares. Consider $b$ knights on black squares and $w$ knights on white squares, so that each knight attacks exactly two other knights. Suppose for the sake of contradiction that $b+w\ge17$ holds.
- Since the $b$ black knights can only be attacked by knights on white squares, and since each knight is attacked by the knights which attack it, by symmetry, we get $b=w$.
- If there is a knight on the (black) central square, consider the eight white squares that are attacked by that knight. Exactly two of these white squares must contain knights, while the other six must be empty. This implies $w\le12-6=6$. Since $b=w$, this means $b+w\le12$, which contradicts the assumption $b+w\ge17$. Hence we will from now on assume that the central square is empty.
- Next assume that there is a knight on one of the four white squares that share an edge with the (black) central square. This knight attacks six black squares, at least four of which must be empty. Together with the empty central square this implies $b\le13-1-4=8$. Since $b=w$, this means $b+w\le16$, which again contradicts the assumption $b+w\ge17$. Hence we will from now on assume that these four white squares are empty.
- In all remaining cases, we are left with $w\le12-4=8$ knights on white squares, and by similar logic, it would be $b+w\le16$.
Therefore $b+w\ge17$ is false. Since we have an example of $b+w=16$, this is an optimal solution.
xnor's answer is correct. Here is why:
Every position has a number that corresponds with the amount of knights a knight can attack.
The best strategy is to remove the knight which can be attacked my most knights until every knight can only hit two other knights.