Skip to main content

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$ and the contradiction. 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$ and the contradiction. 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 the contradictionby 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.

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, 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$ and the contradiction $b+w\le12$. 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$ and the contradiction $b+w\le16$. 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 the contradiction $b+w\le16$.

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.

added 116 characters in body
Source Link
Gamow
  • 45.9k
  • 10
  • 151
  • 387

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, 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$ and the contradiction $b+w\le12$. 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$ and the contradiction $b+w\le16$. 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 the contradiction $b+w\le16$.

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.

  • Since the $b$ black knights can only be attacked by knights on white squares, 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$ and $b+w\le12$. 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$ and $b+w\le16$. 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 $b+w\le16$.

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, 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$ and the contradiction $b+w\le12$. 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$ and the contradiction $b+w\le16$. 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 the contradiction $b+w\le16$.
Source Link
Gamow
  • 45.9k
  • 10
  • 151
  • 387

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.

  • Since the $b$ black knights can only be attacked by knights on white squares, 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$ and $b+w\le12$. 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$ and $b+w\le16$. 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 $b+w\le16$.