6. The figure of the rook threatens any square on the diagonal on which the rook stands on the chessboard. However, if there is a tower on some square of the diagonal, the rook no longer threatens the squares behind it. Determine the maximum number of rooks that can be placed together with four towers on an $8 \times 8$ chessboard so that the rooks do not threaten each other.

(Ján Mazák)
SOLUTION. Each white field lies on one of the seven diagonals parallel to the main white diagonal and marked on the left image with arrows. Similarly, black fields lie on one of the seven diagonals parallel to the main black diagonal. On each of these diagonals without rooks, there can stand at most one archer. Therefore, on an empty chessboard, we can place at most 14 archers.

In the general case, when there are, say, $k$ rooks placed on the chessboard, for each diagonal $D$ of the 14 we consider, we denote $k_{D}$ as the number of rooks standing on it. The integers $k_{D}$ are non-negative and their sum is equal to $k$. The presence of $k_{D}$ rooks delimits at most $k_{D}+1$ segments of fields without rooks on the diagonal $D$, and on each of them, there can be at most one archer, so on the entire diagonal $D$, there are at most $k_{D}+1$ archers. The number of non-threatening archers on the entire chessboard thus does not exceed the sum of 14 numbers $k_{D}+1$, which is equal to $k+14$, i.e., 18 in the case of $k=4$.

![](https://cdn.mathpix.com/cropped/2024_04_17_311860a79a0296bd8ddfg-14.jpg?height=437&width=440&top_left_y=1072&top_left_x=494)

Fig. 3

![](https://cdn.mathpix.com/cropped/2024_04_17_311860a79a0296bd8ddfg-14.jpg?height=389&width=385&top_left_y=1116&top_left_x=1178)

Fig. 4

The right image shows an example of a chessboard with four rooks, on which we have placed 18 archers so that they do not threaten each other.

Answer. The maximum number of archers that can be placed on a chessboard together with four rooks so that the archers do not threaten each other is exactly 18.

GUIDING AND ADDITIONAL PROBLEMS:

N1. What is the maximum number of archers that can be placed on the white fields of an $8 \times 8$ chessboard so that they do not threaten each other? [Seven. On the chessboard, consider diagonals parallel to the main white diagonal. Including it, there are exactly 7 of them. On each, we can place at most one archer. Since each white field lies on one of these diagonals, we can place at most 7 archers on the chessboard. A suitable placement of 7 archers can be chosen, for example, by placing 4 and 3 in the outermost columns of the chessboard.]

N2. Determine the maximum number of archers that we can place on the main white diagonal of an $8 \times 8$ chessboard together with two rooks so that they do not threaten each other in the sense of the competition problem. [Two rooks divide the diagonal into at most three parts. On each, we can place at most one archer. Therefore, the maximum number of archers is three. And we can already place these three archers on the chessboard together with two rooks in the required manner, for example, by placing archers on the first, third, and fifth fields and rooks on the second and fourth fields of the diagonal.]

N3. Determine the maximum number of kings that we can place on an $8 \times 8$ chessboard so that they do not threaten each other. [Divide the chessboard into 16 $2 \times 2$ squares, on each of which we can place at most one king, so the maximum number of kings is 16. We can already place 16 kings on the chessboard, for example, on the fields whose both coordinates are odd.]

N4. Determine the maximum number of kings that we can place on a $9 \times 9$ chessboard so that they do not threaten each other. [By adding one row and one column to the chessboard, we get a $10 \times 10$ chessboard, on which we can place at most 25 kings according to a similar reasoning as in the solution of N3. And we can already place these 25 kings, for example, on the fields whose both coordinates are odd.]

D1. Find the largest natural number $k$ for which it is possible to place $k$ rooks and $k+14$ non-threatening archers on an $8 \times 8$ chessboard. $k=18$. The entire chessboard can be divided into seven white diagonals of lengths $2,4,6,8,6,4,2$ and seven black diagonals of the same lengths. If there are $k_{D}$ rooks on any of these 14 diagonals $D$, there can be at most $k_{D}+1$ non-threatening archers on it. According to the problem, the total number of archers is 14 more than the total number of rooks, so on each considered diagonal $D$, there must be exactly $k_{D}+1$ archers. This is possible for diagonals $D$ of lengths $2,4,6,8$ only if the corresponding $k_{D}$ does not exceed the values $0,1,2,3$ in sequence. Therefore, the number $k$ of rooks on the entire chessboard does not exceed the value $2(0+1+2+3+2+1+0)=18$. The value $k=18$ is possible, as shown by the example of placing 9 rooks and $9+7=16$ archers on white fields according to the image; placing the same number of rooks and archers on black fields can be done analogously.

![](https://cdn.mathpix.com/cropped/2024_04_17_311860a79a0296bd8ddfg-15.jpg?height=394&width=397&top_left_y=411&top_left_x=1429)

D2. Each vertex of a regular 19-gon is colored with one of six colors. Explain why all vertices of some obtuse triangle have the same color. $62-\mathrm{C}-\mathrm{S}-3$

D3. On a $7 \times 7$ board, we play a game of ships. There is one ship of size $2 \times 3$ on it. We can ask about any cell of the board, and if we hit the ship, the game ends. If not, we ask again. Determine the minimum number of questions needed to hit the ship for sure. [58-B-I-4]

D4. On a $5 \times 5$ board, we play a game of ships. Four cells of the board form one ship in the shape of an L-tetromino. We can ask about any cell of the board, and if we hit the ship, the game ends.

a) Propose eight cells to ask about to ensure hitting the ship.

b) Explain why seven questions do not guarantee hitting the ship in general. [58-B-II-2]

D5. On some cell of a $6 \times 6$ chessboard, we place a prince figure. It can jump in one move either vertically or horizontally. The length of this jump alternates between one and two cells, starting with a jump to an adjacent cell. Decide whether it is possible to choose an initial position of the figure so that after a suitable sequence of 35 jumps, it visits each cell of the chessboard exactly once. 65-A-III-6

D6. The cells of an $n \times n$ table, where $n \geqq 3$, are alternately black and white like on a regular chessboard, with the cell in the top left corner being black. We will color the white cells black using the following procedure. In one step, we choose any $2 \times 3$ or $3 \times 2$ rectangle in which there are still three white cells, and we color these three cells black. For which $n$ can we color the entire table black after a certain number of steps? [57-A-II-3]

D7. Determine the smallest natural numbers $k$ for which the following statements a), b), and c) hold: If we place figures on any $k$ cells of an $8 \times 8$ chess