chessboardcombinatoricsrecreational-mathematics
On the chessboard $8 \times 8$ we can to place one rook and several knights. Find the maximum number of knights, which can be placed on a chessboard along with one rook so that none of the pieces attack each other.
My work. If a rook is placed in a square a8, then we can place the $25$ knights in all the white squares that rook doesn’t attack. I do not know how to prove that $25$ is the maximum number of knights.
If $n$ is even, put $n^2/2-1$ knights on the other squares of the same colour of that on which the 1st knight stands.
If $n=2k+1$ is odd, there are $2(k^2+k)+1$ of one colour (say, white) and $2(k^2+k)$ black squares. If the original knight stands on a white square, just put $2(k^2+k)$ knights on the unoccupied white squares. If the original knight stands on a black square it controls at least 3 white squares (because all corner squares are white) and so occupying the remaining $2(k^2+k)-1$ squares gets the maximum.
First of all, here is the proof that you can put no more than $32$ non-attacking knights on a chessboard. You can pair up the squares of the board into $32$ pairs, where each pair is a knight's move apart, as shown below. Since you can place at most one knight in each pair, you can place at most $32$ knights.
Now, imagine placing a queen on some square in this same diagram, and then placing an X on every square attacked by the queen, as well as an X on the squares a knight's move away from the queen. No matter where you place the queen, at least $4$ of these pairs will have both of their squares X'ed out. Therefore, the number of knights you can place is reduced by at least four, so you cannot place more than $28$ knights.
For example, when the queen is placed at $\mathrm A1$, the lower left corner, then the pairs $\mathrm {A1-C2, A2-C1,B2-D1}$, and $\mathrm{A4-C3}$ are all X'ed out (the letter is the column, and the number is the row). It is not too hard to verify case by case that the queen always X's out at least $4$ of these pairs. In fact, as the queen moves closer to the center, she X's out more pairs.
Best Answer
$25$ is the maximum possible and can be proven by case distinction.
First, notice that by a symmetry argument, we can reduce the number of placements for rook to $10$. Here are the possible placements for rook:
Now, there are few observations to make and few facts to be mentioned:
Let $K(n)$ be the maximum number of non-attacking knights that can be placed to $n\times n$ board. Then (source), $$K(n) = \begin{cases} \frac{n^2}{2}, & \text{if $n$ is even} \\[2ex] \frac{n^2+1}{2}, & \text{if $n$ is odd} \end{cases}$$
When we divide a board into $m$ rectangular boards with $K_i$ being the maximum number of non-attacking knights that can be placed to $i^{th}$ small board, we have $$K \le \sum_{i = 1}^m K_m$$ where $K$ is the maximum number of non-attacking knights that can be placed into non-divided board.
We might have different upper bounds for different board divisions. But in the end, we are trying to find the least upper bound.
When we have a $4\times n$ board with $n \ge 2$, maximum number of non-attacking knights that can be placed $K_4(n) = 2n$. For even $n$'s, this is really easy to prove by dividing the board into $2\times4$ small boards. Then we already know $K_4(2) = 4$ (my previous answer). For odd $n$'s, first we should observe $K_4(3) = 6$ (can be seen by trial and error). Then for $K_4(5)$, we are just adding a $2\times4$ board piece to $3\times4$ board. Here, you can use induction to obtain the result.
When we have a $1 \times n$ board, obviously, maximum number of non-attacking knights that can be placed is $n$. But we will try to avoid divisions where we have this case. Instead, we will try the next one.
When we have have a case as in the below where we can't place knights to red line, we can consider left side and right side of the line as a single $2 \times k$ board piece. This is because when we have a $2\times k$ board, whenever we place a knight to left $1\times k$ part, it threatens $1$ or $2$ squares in right $1\times k$ part. Notice that this is the same for the below case.
When we have $3 \times 5$ board, we can place at most $8$ knights. This is also worth mentioning because we will see this case a lot. In order to prove, we can divide it into $3 \times 3$ where maximum is $5$, and $2 \times 3$ where maximum is $4$. So our upper bound is $9$. But, there is only two ways of placing $5$ knights to $3 \times 3$ board (shown below). In both cases, you can see that we can't place more than $3$ knights to $2 \times 3$ board. Therefore, $9$ is not achievable. Note that this will be our main proof idea from here onward.
Now, we can look at the cases. I will write the maximum number of knights to each division and red notches will indicate where knights can threaten the rook (therefore we can't place knights):
Case 1: Rook in a1. This is an easy case since it leaves us with $7 \times 7$ board where we can't place knights to two of white squares. but on that $7 \times 7$ board, there are $25$ black squares. So we have $K_{a1} \le K(7) = \frac{7^2+1}{2} = 25$ by the first fact and indeed we can place $25$ knights as you suggested.
Case 2: Rook in b1. We can divide the board as in the following:
Here, we have $26$ as upper bound. However, this is still not bad because in order to achieve $26$, all the divisions must have maximum possible of knights. Therefore, whenever we prove we can't achieve maximum for a division, upper bound becocmes $25$.
Now, for blue part of the board, placement of $8$ knights is unique (shown below). And when we make that placement, $3$ squares of $3 \times 5$ board is threatened (shown by black notches). And dividing it into a $3 \times 3$ and a $2 \times 3$ board, if we use all $3$ unthreatened squares of $2 \times 3$, we can't place $5$ knights to $3 \times 3$ board. Therefore, we can't place $8$ knights to blue part and $3 \times 5$ board. Therefore, $26$ is not achievable in this case.
Case 3: Rook in b2. We can divide the board as in the following:
Here, we have $K_{b2} \le 25 = 13+6+4+2$.
Case 4: Rook in c1. We can divide the board as in the following:
Here, again we have $26$ as an upper bound. But if we focus left side of the board, we can see that if we place $2$ knights to $2 \times 2$ board, we can't place $6$ knights to $2 \times 5$ board (shown below). Therefore, $26$ is not achievable in this case.
Case 5: Rook in c2. We can divide the board as in the following:
Here, we have $26$ as an upper bound. But green part has a unique placement for $6$ knights (shown below). After that placement, we can observe that for $2 \times 5$ board, placement of $5$ knights is determined. After that, we should notice we can't place $8$ knights to $3 \times 5$ board. Therefore, $26$ is not achievable.
Case 6: Rook in c3. We can divide the board as the following:
Then, we have $K_{c3} \le 25 = 13+5+5+2$.
Case 7: Rook in d1. We can divide the board as the following:
Then, we have $K_{d1} \le 25 = 14+6+5$.
Case 8: Rook in d2. We can divide the board as the following:
Here, again we have $26$ as an upper bound. But it is easy to see that if we place $4$ knights to blue part, we can't place maximum of $2$ knights to $2 \times 1$ board. Therefore, $26$ is not achievable in this case.
Case 9: Rook in d3. We can divide the board as the following:
Then, we have $K_{d3} \le 25 = 10+8+4+3$.
Case 10: Rook in d4. We can divide the board as the following:
Then, we have $K_{d4} \le 25 = 8+6+6+5$.
Therefore, the maximum possible number is $25$.
Unfortunately, this is a very long solution and in some of $10$ cases, we found upper bound to be $26$ and forced to prove $26$ was not possible (maybe there are some divisions of board where $25$ is upper bound for these bad cases). I couldn't see a way to show $25$ is the maximum possible without a case distinction of rook placements. If there is an easier way, I am also glad to see that.