Maximal number of kings on a chessboard, but this time two can be adjacent.

Question

How many kings can be placed on an $8 \times 8$ chessboard such that every king can capture (is adjacent to) at most one other king? I can do 26, but can not prove that this is optimal.

Answer 1

$26$ is optimal.

First, extend the $8 \times 8$ chess board to a $9 \times 9$ Torus board. If you're unfamiliar with how this works, we add an additional row and column to the board, and we consider opposite edges of the board to be adjacent--when you go off one edge of the board, you come back on the opposite side. For example, a king in one of the corners can capture a piece in any of the other three corners. For a relevant explanation of how Torus chess would work on an $8 \times 8$ board, see here.

Extending the board in this way makes life easier because now every square is adjacent to exactly 8 other squares. And since any valid $8 \times 8$ position of kings translates to a valid $9 \times 9$ position of kings (with the additional row and column both empty), it suffices to show that at most $26$ kings fit on the $9 \times 9$ Torus board.

Suppose we have $n$ kings on the Torus board. Each king will be a member of one of three possible formations:

Formation A:

----
-KK-
----

Formation B:

----
-K--
--K-
----

Formation C:

---
-K-
---

Now, suppose each board square has side length $1$ unit. Draw a $2 \times 2$ square centered at each king, i.e., a square which extends half a unit left, right, above, and below the king. Call this square a king's "domain". Then two kings are adjacent if and only if their domains intersect. It follows that we can draw the "total" domain for each of the formations A, B, and C (the union of the individual kings' domains for that formation), and that no two different formations will have intersecting domains.

• The domain of formation A is a rectangle of dimensions $2 \times 3$, so it has area $6$.

• The domain of formation B is two $2 \times 2$ squares minus their $1 \times 1$ intersection, so it has area $7$.

• The domain of formation C is just a $2 \times 2$ square, with area $4$.

Let $a$, $b$, and $c$ be the number of occurences of formations $A$, $B$, and $C$, respectively. Then $2a + 2b + c = n$. Moreover, counting the total area that is taken up across all formations' domains, we get $$ 6a + 7b + 4c \le 81 $$

Then, $$ 3n = 6a + 6b + 3c \le 6a + 7b + 4c \le 81 $$ implying $n \le 27$. But if $n = 27$, then by parity $c \ge 1$, so $3c < 4c$, so $$ 3n = 6a + 6b + 3c < 6a + 7b + 4c \le 81 $$

Therefore, $n$ is at most $26$.