How many bishops can be placed on a $m \times n$ chessboard?

Solution 1:

The answer is sometimes $m+n-2$ and sometimes $m+n-1.$

To show that these are the correct answers, and find the cases in which each answer applies, we can do two things: first, find an upper bound on the number of bishops in each possible case, so we know there cannot be more bishops; then show in each case that this upper bound can be achieved by actually placing bishops on the board.

Proving an upper bound

Since bishops on different colored squares can never attack each other, we can find the maximum number of bishops by placing as many as we can on black squares and as many as we can on white square and adding the two numbers together.

It may also help visualization if you turn the board $45$ degrees as shown in this answer. Then the black squares are arranged in some number of rows and columns (with squares missing in the corners of that array) and similarly with the white squares. Since bishops attack along rows and columns of this rotated array, the number of bishops on black squares cannot be more than the number of black rows or the number of black columns, whichever is less. Similarly with white squares.

But we can do the same counting while keeping the board in its usual orientation if we say "left diagonals" and "right diagonals" instead of "rows" and "columns."

An easy way to count right and left diagonals of black squares is to count black squares along the left edge and bottom edge of the board, then along the bottom edge and right edge. Likewise, we do this for the white squares. There are $m + n - 1$ total squares (black and white) along two adjacent edges, but the number of squares of each individual color depends on the parity of $m$ and $n$ (and sometimes on which color is chosen for a corner square, but that does not affect the final total, only how the bishops are distributed between the two colors of square).

Case where $m$ and $n$ are both even. In this case, adjacent corners have opposite colors. Counting squares along pairs of adjacent sides, we will find $\frac12(m+n)$ black squares one one pair of sides and $\frac12(m+n) - 1$ on the other, so there can be at most $\frac12(m+n) - 1$ bishops on black squares. Same for white.

This puts an upper bound on the number of bishops at $$2\left(\frac12(m+n) - 1 \right) = m + n - 2.$$

Case where $m$ and $n$ have opposite parities. In this case, whichever two adjacent sides you pick, you will find an equal number of black and white squares, $\frac12(m+n-1)$ of each color. This gives us a maximum of $\frac12(m+n-1)$ bishops on each color square.

This puts an upper bound on the number of bishops at $$2\left(\frac12(m + n - 1)\right) = m + n - 1.$$

Case where $m$ and $n$ are both odd. In this case, all four corners are the same color. Counting squares along any pair of adjacent sides, we will find $\frac12(m+n)$ squares the same color as the corner and $\frac12(m+n) - 1$ squares of the other color. So there are at most $\frac12(m+n)$ bishops on one color and $\frac12(m+n) - 1$ on the other.

This puts an upper bound on the number of bishops at $$\frac12(m+n) + \left(\frac12(m+n) - 1\right) = m + n - 1.$$

But there is one further wrinkle: if $m = n$ and $m$ is odd, then supposing the corner squares are black, the first and last right diagonal of black squares have only one square each and these two squares are on the same right diagonal. So we cannot occupy all $\frac12(m+n)$ right diagonals, only $\frac12(m+n) - 1$ of them. So in this special case the upper bound on the number of bishops is $$2\left(\frac12(m+n) - 1 \right) = m + n - 2.$$

Demonstrating that the bound can be achieved

Case where $m$ and $n$ are both even. If $m = n,$ put $m - 1$ bishops along the left edge of the board, in all squares except the top left corner. Likewise place $m - 1$ bishops long the right edge of the board except in the top right corner. Total: $m + n - 2.$

If $m \neq n$, without loss of generality suppose $m < n$ and suppose the board is rotated so that its long edges are horizontal. Put $m$ bishops along the left edge and $m$ bishops along the right edge. In the case where $n = m+2$ this achieves $m + n - 2$ bishops; if $n > m + 2$ there will be a rectangle of unattacked squares of height $2$ and width $n - m - 2$ in the middle of the board. Put $n - m - 2$ bishops in this rectangle, either along one long edge or in alternating squares along both upper and lower edges as in the figure below (which shows an arrangement of bishops for the case $m=6,$ $n=12$).

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \mathrm{B} &&&&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \mathrm{B} & \phantom{\mathrm{B}} & \mathrm{B} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \mathrm{B} \\ \hline \mathrm{B} &&&& \mathrm{B}&& \mathrm{B} &&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&&&& \mathrm{B} \\ \hline \end{array}

This gives a total of $2m + (n - m - 2) = n + m - 2$ bishops.

Case where $m$ and $n$ have opposite parities. Without loss of generality, suppose $m < n$ and suppose the long edge of the board is horizontal. We start by placing $m$ bishops along the left edge and $m$ along the right edge. Then we place some bishops in the unattacked squares in the middle of the board, if there are any. For that step we break this case into two sub-cases.

Sub-case where $m$ is odd. In this case there is a horizontal row of $n - m - 1$ unattacked squares in the middle of the board; put bishops in all of those squares. For example, with $m=5$ and $n=10$ we have this arrangement:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \mathrm{B} &&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \mathrm{B} & \mathrm{B} & \mathrm{B} & \mathrm{B} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&& \mathrm{B} \\ \hline \end{array}

This gives a total of $2m + (n - m - 1) = n + m - 1$ bishops.

Sub-case where $m$ is even. In this case there is a rectangle of height $2$ and width $n - m - 2$ of unattacked squares in the middle of the board; put bishops in alternating squares along the top and bottom edges of that rectangle, starting at the left edge. For example, with $m=6$ and $n=11$ we have this arrangement:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline \mathrm{B} &&&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \mathrm{B} & \phantom{\mathrm{B}} & \mathrm{B} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \phantom{\mathrm{B}} & \mathrm{B} \\ \hline \mathrm{B} &&&& \mathrm{B}&& \mathrm{B} &&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&&& \mathrm{B} \\ \hline \mathrm{B} &&&&&&&&&& \mathrm{B} \\ \hline \end{array}

In this way we have $\frac12(n - m - 1)$ occupied squares and $\frac12(n - m - 3)$ unoccupied squares along each long edge of the rectangle in the middle, for a total of $n - m - 1$ bishops in that rectangle and $2m + (n - m - 1) = n + m - 1$ bishops on the entire board.

Case where $m$ and $n$ are both odd. If $m = n$, place $m - 1$ bishops along the left edge and $m - 1$ along the right edge as in the case where $m$ and $n$ are both even, for a total of $m + n - 2$ bishops.

If $m \neq n$, as before assume $m < n$ and the long edge of the board is horizontal. Arrange the bishops similarly to the the arrangement for $m$ odd, $n$ even, and $m < n$, that is, $m$ bishops along the left edge, $m$ along the right edge, and a horizontal row of $n - m - 1$ bishops in the middle of the board, for $2m + (n - m - 1) = n + m - 1$ bishops altogether.

That covers all cases, and in each case we have demonstrated that the upper bound proved in the first half of the answer can be achieved.

Summary

Merging cases together depending on which answer they give, we have the following results:

If $m$ and $n$ are both even, or if $m = n$, the total number of bishops that can be placed is $m + n - 2.$

In all other cases, the total number of bishops that can be placed is $m + n - 1.$