38. a) What is the smallest number of kings that can be placed on a chessboard of 64 squares so that these kings threaten all the squares free of figures?

b) The same question for a chessboard of $n^{2}$ squares.
38. a) Let's divide the board into nine parts as indicated in Fig. $46, \alpha$. In each of these parts, there is a cell (marked with a circle in Fig. 46, $a$) that can only be threatened by kings standing on cells of the same part. Therefore, for all fields of the board to be under threat, there must be at least one king in each of the nine parts. From this, it is clear that the required number of kings cannot be less than 9. But nine kings can be placed so that they threaten all the fields of the board: such an arrangement is indicated, for example, by circles in Fig. 46, $a$. Thus, the required minimum number of kings is 9.

b) The problem is solved similarly to part a); only here we need to consider three cases separately: the case where $n$ is divisible by 3, the case where $n$ gives a remainder of 2 when divided by 3, and the case where $n$ gives a remainder of 1 when divided by 3.

If $n$ is divisible by 3, i.e., $n=3 k$, then the board can be divided into $k^{2}=\left(\frac{n}{3}\right)^{2}$ squares of nine cells each (see Fig. $46, \sigma$, where $n=9$); in each of these squares, there must be at least one king, otherwise not all centers of such squares will be under threat. Since $k^{2}=\frac{n^{2}}{9}$ kings can always be placed on a board of $n^{2}=(3 k)^{2}$ cells so that they threaten all the fields of the board (it is sufficient to place them in the centers of the squares of nine cells, into which the board is divided; see Fig. 46, b), the required minimum number of kings for $n=3 k$ is $k^{2}=\frac{n^{2}}{9}$.

If $n$ gives a remainder of 2 when divided by 3, i.e., $n=3 k+2$, then the board is divided into $(k+1)^{2}=\left(\frac{n+1}{3}\right)^{2}$ smaller parts in exactly the same way as we did in the case of $n=8, k=2$ (see Fig. $46, a$). From the consideration of this division, it follows that for $n=3 k+2$, the required minimum number of kings is

$$
(k+1)^{2}=\frac{(n+1)^{2}}{9}
$$

Finally, if $n$ gives a remainder of 1 when divided by 3, i.e., $n=3 k+4^{1}$, then the board is divided into

$$
(k+2)^{2}=\left(\frac{n+2}{3}\right)^{2}
$$

smaller parts as shown in Fig. 46, c (where $n=10, k=2$). From the consideration of this diagram, it is easy to conclude that for $n=3 k+4$, the required minimum number of kings is

$$
(k+2)^{2}=\frac{(n+2)^{2}}{9}
$$

The only case where $n$ cannot be represented as $3 k, 3 k+2$, or $3 k+4$ is the case $n=1$; but in this case, it is obvious that the required number of kings is 1, i.e., it is also equal to $\frac{(n+2)^{2}}{9}$.

Using the notation for the integer part, the obtained results can be combined as follows: the minimum number of kings that can be placed on a chessboard of $n^{2}$ cells so that they threaten all the fields of the board is $\left[\frac{n+2}{3}\right]^{2}$.

Note. From the consideration of Fig. 46, b, it is not difficult to see that for $n$ divisible by 3, there is a unique arrangement of $\left(\frac{n}{3}\right)^{2}$ kings on an $n^{2}$-cell board such that all fields of the board are under threat. For $n$ giving a remainder of 1 or 2 when divided by 3, the minimum possible number of kings that threaten all the fields of the board can be placed on the board in many different ways; the calculation of this number of ways we leave to the reader.

1) Any positive integer $n$, except $n=1$, giving a remainder of 1 when divided by 3, can be represented as $n=3 k+4$, where $k$ is a non-negative integer. The case $n=1$ we will consider separately.