3
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

Here's 16:

. X X X .
X X . X X
X . . . X
X X . X X
. X X X .
$\endgroup$
  • 2
    $\begingroup$ Can you however prove this is a maximum? $\endgroup$ – Tim Couwelier Feb 25 '15 at 10:15
  • 1
    $\begingroup$ Nope, but I'm thinking about it. $\endgroup$ – xnor Feb 25 '15 at 10:34
  • 4
    $\begingroup$ I wrote a brute force code to check all the 2^25 possibilities, this is indeed the best solution. $\endgroup$ – Raziman T V Feb 25 '15 at 10:58
  • 1
    $\begingroup$ @ThePopMachine He gets an extra 2 rep by accepting someone else's answer! $\endgroup$ – Rand al'Thor Mar 14 '15 at 18:45
  • 1
    $\begingroup$ @ThePopMachine Excellent idea! I believe this is acceptable practice, since the aim of SE is to provide good-quality answers regardless of who posts them. If you edit Gamow's answers into xnor's, then Gamow can delete his answer and all's well. $\endgroup$ – Rand al'Thor Mar 14 '15 at 19:23
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I added an explanation to the first bullet, but I don't see the leap in the second bullet that tells you that the four white squares must be empty. What you stated doesn't preclude w=b=8. Am I missing something? If so, please add a little more explanation. $\endgroup$ – ThePopMachine Mar 14 '15 at 18:01
  • $\begingroup$ OK, I got it, and agree. But I'm going to add a little more language to make the train of thought easier to follow. $\endgroup$ – ThePopMachine Mar 14 '15 at 18:18
4
$\begingroup$

xnor's answer is correct. Here is why:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ It doesn't guarantee to find the optimal position. The count counts equally "knight-step" neighbours that have too many neighbours and neighbours that have the ideal 2. Removing the 6 on the second step forces to also remove 2 corners. $\endgroup$ – Florian F Feb 25 '15 at 15:49
  • $\begingroup$ @FlorianF, why should there be knights in a corner if that isn't the optimal solution? $\endgroup$ – Jordy Feb 25 '15 at 16:09
  • $\begingroup$ I don't say it is not optimal. But if you already have knights that attack exactly 2 others, which is what you want in the end, it is a pitty to remove them. How can you be sure this process leads to an optimal solution? $\endgroup$ – Florian F Feb 25 '15 at 17:06
  • 2
    $\begingroup$ "The best strategy is to remove the knight which can be attacked my most knights until every knight can only hit two other knights." This is not true on general board shapes. Why should it be true here? $\endgroup$ – Lopsy Feb 25 '15 at 21:55
  • 2
    $\begingroup$ @Jordy: I'm voting down because you say xnor's answer is correct (i.e. optimal) but nothing about your arguments proves it is optimal, as others have pointed out. Therefore your answer is technically false unless you can somehow improve it. $\endgroup$ – ThePopMachine Mar 14 '15 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.