Prove that if fifteen bishops were placed on a chessboard, then at least two of them attack each other.
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.
Solution 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).
Solution 2:
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.