Prove that if fifteen bishops were placed on a chessboard, then at least two of them attack each other.

Question

Prove that if fifteen bishops were placed on a chessboard, then at least two of them attack each other.

I was wondering if the following method is correct? (I also feel like I cheated a bit, as if they asked me the minimum bishops needed instead of saying 15, it would've been harder. I took 15, subtracted 1, and knew I had to occupy 14 spots somehow.)

I think the way I did it is a bit clunky, and isn't obvious in showing that it's the "worst" case scenario. What I did was place 7 bishops on the top row, except the top right corner, then 7 bishops in the bottom row except the right bottom corner. So now a 15th bishop must be placed in any of the attacking range of the other bishops (by the Pigeonhole Principle).

A lot of the time, I feel like I'm just using intuition, rather than being able to pick out the correct pigeons and pigeonholes.

Answer 1

No, this isn't a proof because as you say there's no reason why putting the first $14$ bishops in those positions is the best way to start.

The way to do this sort of problem is usually to divide the board up into sections such that any two pieces in the same section are attacking, while also making sure there are more pieces than sections, so that pigeonhole ensures there are two in the same section. (An easier example of the same sort of thing: if you put $9$ rooks on a chessboard, some two must be attacking, because there are only $8$ rows so by pigeonhole you have two in the same row.)

So here, you should be trying to cover the board with $14$ diagonals (hint: try to cover the white squares with $7$ diagonals).

Answer 2

We have the "falling" diagonal a8-h1 and the thirteen "rising" diagonals a7-b8, a6-c8, a5-d8, ..., g1-h2, which together cover all of the board. As each of these fourteen diagonals can contain at most one bishop in a non-attacking configuration, there canot be more than 14 bishops.

Answer 3

assume we have a chess board:

$$(1,1) , (1,2) ,..., (1,8) \\ (2,1) , (2,2) ,..., (2,8) \\ ... \\ (8,1) , (8,2),..., (8,8) $$

lets define the diagonal $d_1 = ${$ (8,1) $} , $d_2 = ${$ (7,1),(8,2) $} ,..., $d_8 = ${$ (1,1) , (2,2) ,...,(8,8) $} , ... , $d_{15} = ${$ (1,8) $}.

then :

case 1 - every bishop is in a diferent diagonal then there are bishops in (8,1) and (1,8) and they attack each other

case 2 - one of the diagonals $d_1 \ or \ d_{15}$ is empty then by pigeon hole (diagonals = holes , bishops = pigeons) there are at least two bishops in the same diagonal --> they attack each other.

Answer 4

The easiest way I see to prove this via the pigeonhole is:

If you re-align the board as a diamond you can treat the white squares as a diamond shaped grid that's 8x7 where bishops move as rooks.

Since there are only 7 columns, there can be no solution beyond 7 in which two bishops are not in the same column (and thus attacking one another). This is also true for the black squares, which just a 90 degree rotation of the white squares. Therefore, using both colors, there are only 14 pigeonholes.

Answer 5

Since there are only 15 diagonal lines in either the a1-h8 or a8-h1 direction (including the corner squares), each bishop must be placed on a different diagonal in order to avoid mutual attacks. This means that, however you arrange the pieces, two diagonally opposite corners must be occupied. The only way that you can avoid this is to place some two other pieces on another diagonal.

Answer 6

We can even prove more general statement about this.We can prove that in any $n×n$ chess board we can place at most $2n-2$ non-attacking bishops.

The proof of this statement is an easy consequence of Pigeonhole-principle.

In an $n×n$ chessboard there are total $2n-1$ diagonal parallel to the principle diagonal and including the two opposite corners.Then if we place at least $2n-1$ bishops then either both the two opposite corners will contain one bishop ,hence they won't be non-attacking,or at least one diagonal will contain two bishops and they will attack.Hence we can place at most $2n-2$ bishops in non-attacking position in an $n×n$ chessboard.Then for $n=8$ we can place at most $14$ non-attacking bishops.