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

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).


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.

enter image description here

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.


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.

Tags:

Pigeonhole Principle

Chessboard

Related

Showing that $\lvert H K\rvert = \frac{| H\| K|}{ |H\cap K|}$ $a_n$ is the smallest positive integer number such that $\sqrt{a_n+\sqrt{a_{n-1}+...+\sqrt{a_1}}}$ is positive integer Prove that $\lim\limits_{x\to 0^+}\sum\limits_{n=1}^\infty\frac{(-1)^n}{n^x}=-\frac12$ Is the set of rational number discrete or continuous? How does calculus without Euler's number (e) look? Prove the existence of an analytic function Is the algebraic number theory in Ireland and Rosen enough to study Washington's Cyclotomic Fields? Why do I get a converging result when pressing cosine multiple times on a calculator? Why only two tangents can be drawn to a parabola from a point outside it? The $0^{\rm th}$ prime number proving that a function from $\Bbb R^2$ to $\Bbb R^2$ is surjective Why doesn't $c_0$ admit a complement in $l^\infty$?

Recent Posts