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?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
10
Here's 16:
. X X X .
X X . X X
X . . . X
X X . X X
. X X X .
-
2$\begingroup$ Can you however prove this is a maximum? $\endgroup$ Commented Feb 25, 2015 at 10:15
-
1
-
4$\begingroup$ I wrote a brute force code to check all the 2^25 possibilities, this is indeed the best solution. $\endgroup$ Commented Feb 25, 2015 at 10:58
-
1$\begingroup$ @ThePopMachine He gets an extra 2 rep by accepting someone else's answer! $\endgroup$ Commented Mar 14, 2015 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$ Commented Mar 14, 2015 at 19:23
$\begingroup$
$\endgroup$
2
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.
-
$\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$ Commented Mar 14, 2015 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$ Commented Mar 14, 2015 at 18:18
$\begingroup$
$\endgroup$
9
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.
-
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$ Commented Feb 25, 2015 at 15:49
-
$\begingroup$ @FlorianF, why should there be knights in a corner if that isn't the optimal solution? $\endgroup$ Commented Feb 25, 2015 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$ Commented Feb 25, 2015 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$– LopsyCommented Feb 25, 2015 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$ Commented Mar 14, 2015 at 17:52