4. What is the maximum number of chess kings that can be placed on a $12 \times 12$ board so that each king attacks exactly one of the others?
Answer: 56.

Solution. Note that two kings attack each other if and only if their cells share at least one vertex. For each pair of attacking kings, mark the vertices of the cells they occupy. In this case, no fewer than six vertices are marked for each such pair. Since different pairs of kings mark different vertices (otherwise, some king would attack more than one king), the total number of pairs of kings is no more than $\left[13^{2} / 6\right]=28$, and the number of kings is no more than 56.

The arrangement of 56 kings is shown in the figure.

![](https://cdn.mathpix.com/cropped/2024_05_06_2372c6c7172c9d69ac50g-06.jpg?height=434&width=440&top_left_y=1705&top_left_x=928)