It Is Unbecoming For Bishops To Attack Each Other

Probability Level 3

Find the maximum number of non-attacking bishops that can be placed on a $101$ x $101$ chessboard.

The answer is 200.

3 solutions

Eddie The Head
Apr 21, 2014

$\textbf{Solution outline:}$

We will try to prove it for a more general case ,that is,for an (2n-1)x(2n-1) chessboard.To make visualisation easier I have drawn an 11x 11 chessboard.

We are drawing diagonal elements from the top right block of the board to the downright corner(As shown by the figure on the right).,Clearly (2n-1) such diagonals are possible to be drawn.Note that each diagonal can contain atmost one bishop. But in this case for the middlemost diagonal while covering the 2 corner squares we will have 2 attacking bishops(shown by crosses in the figure to the right).So at most (2n-2) bishops are possible and figure 2 shows the arrangement of the bishops in an 11x11 chessboard and following a similar algorithm we can cover a (2n-1)x(2n-1) chessboard.

So here $n = 101$ and hence the maximum number of bishops possible is $2*101-2 = 200$ .

imj imj

Instead of "top right block of the board to the downright corner", do you mean "top left"?

You need to justify why we can't have $2n-1$ bishops better. Your current claim doesn't necessarily hold (or I might be interpreting you wrong).

This is how I would do it: Consider the $2n-1$ diagonals that go from the top left to the bottom right. There are at most 1 bishop on each of these diagonals, hence at most $2n - 1$ bishops. However, if we had $2n-1$ bishops, this means that there must be a bishop in the lower left square (since it's the only square in its top-left bottom-right diagonal) and the upper right square (since it's the only square in its top-left bottom-right diagonal). These results in 2 bishops that can attach each other.
Hence, we can have at most $2n - 2$ bishops. It's easy to find such an arrangement.

Note that I used a pigeonhole / construction existence argument to force there to be bishops in the corner squares.

Calvin Lin Staff - 7 years, 1 month ago

Yes Sir,I also solved it in this way but here I just put an outline...maybe I'll have to make it a better solution.

Eddie The Head - 7 years, 1 month ago

If we assume that bishops are same color(white or black), and they can't attack each other because they are in the same team, you can place 101 x 101 = 10201 bishops.

Branislav Dinic - 7 years, 1 month ago

http://mathworld.wolfram.com/BishopsProblem.html

Peter Herbert - 7 years, 1 month ago

Kp Govind
Apr 21, 2014

As the objective is to have the maximum number of bishops which do not attack each other, the number will be reduced if we have pieces near the centre, as they will then attack each other. Therefore, the pieces have to be placed on any two opposite ends of the board. One whole end can be filled, but the other end's corners cannot be filled as it would be attacked.

So for a 10x10 chessboard, the maximum number is 10+8=18

For a 101x101 chessboard it will be 101+99= 200 which is the required answer.

A general formula for any n x n chessboard with n > 1 would be x = 2 * n - 2, where x represents the maximum number of bishops, following the same logic.

Eduardo Nunes - 7 years, 1 month ago

You have to substantiate the claim of "the number will be reduced if we have pieces near the centre". It is not immediately obvious that in the maximum case, all the pieces must be at the side.

Calvin Lin Staff - 7 years, 1 month ago

Maheswara Murthy
Apr 23, 2014

n=101 x=(2*n)-2=200

It Is Unbecoming For Bishops To Attack Each Other

The answer is 200.

3 solutions

0 pending reports