21
$\begingroup$

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.

$\endgroup$
4
  • 12
    $\begingroup$ The statement you are attempting to prove does not ask if there exists (at least) one arrangement of 15 bishops where at least two of them attack each other. It asks if all ways of placing 15 bishops on a board must have at least two of them attacking each other. How does your proposed arrangement speak to any other arrangement? $\endgroup$
    – Eric Towers
    Commented Oct 13, 2017 at 13:22
  • 2
    $\begingroup$ It may help to simplify the problem for you if you realize that this is equivalent to saying that 8 bishops on the same color must have at least one mutual attack. After all, blacks cannot attack whites, and vice versa. $\endgroup$
    – WhatRoughBeast
    Commented Oct 13, 2017 at 19:04
  • 1
    $\begingroup$ You've accepted an answer but it's based on a mischaracterization of what you said. Your configuration is one stage in a very valid proof of the problem. If you add the preliminary reasoning, then you have a proof. $\endgroup$
    – Spencer
    Commented Oct 14, 2017 at 13:47
  • $\begingroup$ Using: meta.stackexchange.com/questions/145677/… - The first point is true. I found difficulty in conceptualizing the question, put out my thoughts on why I think the answer I found is not a valid proof and to see valid proofs on the question. I'm not sure if you would personally find it useful but it was useful to me and maybe other readers as well. $\endgroup$
    – hs_math_enjoyer
    Commented Oct 15, 2017 at 5:23

6 Answers 6

Reset to default
32
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks! I'm havign a bit of trouble with this. When you say "cover the board with $14$ diagonals", covering the white squares with $7$, do I still keep in the mindset of "choosing the optimal setup" for the board? $\endgroup$
    – hs_math_enjoyer
    Commented Oct 13, 2017 at 9:31
  • $\begingroup$ Oh, is this adequate (or intended)?: Start with the top left white square. Then go across the top row to the right (marking the "left to right" diagonals) and down the last column marking the "right to left" diagonals). There are $7$ of these. Then, similarly for the black squares, start at top right, go to left then down 1st column. I think this covers the $14$ diagonals? $\endgroup$
    – hs_math_enjoyer
    Commented Oct 13, 2017 at 9:41
  • $\begingroup$ @ActuarialStudent101: I may be misunderstanding but if you go down the right column then all the white squares there can be attacked by your bishops in the top row. The obvious three remaining places are the bottom row. $\endgroup$
    – Chris
    Commented Oct 13, 2017 at 10:07
  • 7
    $\begingroup$ Just to illustrate this: If I place 8 bishops on the 4th row, I cannot place a 9th. It does not follow that it is not possible to place 9 bishops. $\endgroup$
    – Carsten S
    Commented Oct 13, 2017 at 13:08
20
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Simple! Thanks. I see that the aim is just to label the total amount of possible diagonals, and see that a $15th$ bishop will fall on to a pre-existing diagonal. $\endgroup$
    – hs_math_enjoyer
    Commented Oct 15, 2017 at 5:25
  • $\begingroup$ @ActuarialStudent101 It's worth noting this only proves the upper bound: There can be no solution with more than 14 bishops. It doesn't actually show that there is a 14 hole solution, so with just this it could be smaller. But since your question was 15, it fits that bill. $\endgroup$
    – TemporalWolf
    Commented Oct 16, 2017 at 2:48
  • $\begingroup$ But it does show that $15$ is the lowest upper bound right? To show a $14$ hole solution we'd just need to find an example? $\endgroup$
    – hs_math_enjoyer
    Commented Oct 18, 2017 at 21:50
  • 2
    $\begingroup$ @ActuarialStudent101 This proves there can be no more than 14 pigeon holes, so 15 cannot be correct: I don't need to find a 14 solution to prove that. It could be fewer, but it can't be more. If you can find a 14 hole solution, that proves there are at least 14 pigeon holes. Together, they prove that this problem has exactly 14 pigeon holes: You can place 14 bishops with no collisions and no more. $\endgroup$
    – TemporalWolf
    Commented Oct 18, 2017 at 22:02
14
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Fine. Or more symmetrically, cover the black squares with $7$ rising diagonals and the white squares with $7$ falling diagonals. Or cover the whole board with $15$ rising diagonals to show that $16$ bishops are impossible, and note the the maximum number of bishops must be an even number. $\endgroup$
    – bof
    Commented Oct 13, 2017 at 8:55
  • $\begingroup$ @bof It is not obivious (to me!) why the maximum number of bishops must be even. But you don't need that assertion. If you place a bishop on each of the rising 15 diagonals, the two bishops on the "end" diagonals (of length one square) either attack each other, or attack another bishop which was placed between them on the longest falling diagonal. So at least two of the 15 will always attack each other. You can easily construct a configuration of 14 non-attacking bishops, of course, so 15 is the minimal solution. $\endgroup$
    – alephzero
    Commented Oct 14, 2017 at 4:12
  • 1
    $\begingroup$ @alephzero Why the maximum number of bishops must be even? Since a bishop moves on squares of one color, the maximum number of bishops is equal to the maximum number of white-squared bishops plus the maximum number of black-squared bishops. To see that the two summands are equal, observe that a 90 degree rotation swaps white squares with black squares. $\endgroup$
    – bof
    Commented Oct 14, 2017 at 4:29
  • 2
    $\begingroup$ @alephzero In other words, the bishop's graph has two connected components, which are isomorphic to each other. For such a graph the independence number is even. $\endgroup$
    – bof
    Commented Oct 14, 2017 at 4:43
10
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .