37. a) What is the maximum number of kings that can be placed on a chessboard of 64 squares so that no two kings threaten each other?

b) The same question for a chessboard of $n^{2}$ squares.
37. a) Let's divide the chessboard into 16 squares, each consisting of four cells, as shown in Fig. 45, a. When placing kings so that no two of them threaten each other, in each of these 16 squares, there can be no more than one king. Therefore, it is impossible to place more than 16 kings so that they do not threaten each other. However, 16 kings, none of which threaten each other, can be placed on a chessboard of 64 cells; this is evident, for example, from Fig. 45, a. Therefore, the maximum number of kings sought is 16.
b) If the number \( n \) is even: \( n = 2k \), then the problem is solved in the same way as in part a). Specifically, in this case, the board is divided into \(\left(\frac{n}{2}\right)^2 = k^2\) small squares of four cells each. From the fact that in each of these squares, two kings cannot be placed without threatening each other, it follows that the sought number of kings cannot exceed \( k^2 \). But \( k^2 \) kings.

![](https://cdn.mathpix.com/cropped/2024_05_21_68334347b64402497ba5g-161.jpg?height=393&width=396&top_left_y=507&top_left_x=192)
a)

![](https://cdn.mathpix.com/cropped/2024_05_21_68334347b64402497ba5g-161.jpg?height=452&width=446&top_left_y=449&top_left_x=681)

b)

Fig. 45.

not threatening each other, can certainly be placed on a board of \((2k)^2\) cells; for this, it is sufficient, for example, to arrange them similarly to how it is shown in Fig. 45, a for the case \( n = 8 \). From this, it follows that for even \( n \), the maximum number of kings sought is \(\frac{n^2}{4}\).

Now let the number \( n \) be odd: \( n = 2k + 1 \). Divide the board into

\[
\left(\frac{n+1}{2}\right)^2 = (k+1)^2
\]

smaller parts as indicated in Fig. 45, b (with such a division, we get \( k^2 \) squares consisting of four cells, \( 2k \) rectangles consisting of two cells, and one small square of one cell, i.e., a total of \( k^2 + 2k + 1 = (k+1)^2 \) parts). It is clear that in each of these parts, no more than one king can be placed (if it is required that the kings do not threaten each other). Therefore, the total number of kings cannot exceed \((k+1)^2\). But \((k+1)^2\) kings can be placed, as seen in Fig. 45, b, where \( k = 4 \). Therefore, the maximum number of kings sought is

\[
(k+1)^2 = \frac{(n+1)^2}{4}.
\]

Using the notation for the integer part introduced on page 13, the results for the cases of even and odd \( n \) can be combined: the maximum number of kings that can be placed on a board of \( n^2 \) cells so that no two of them threaten each other is \(\left[\frac{n+1}{2}\right]^2\).

Remark. From the consideration of Fig. 45, b, it is not difficult to conclude that for odd \( n \), there is a unique arrangement of \(\frac{(n+1)^2}{4}\) kings on an \( n^2 \)-cell board, in which no two kings threaten each other. For even \( n \) (in particular, for \( n = 8 \)), the maximum possible number of kings that do not threaten each other can be placed on the board in many different ways. Calculating this number