Find the maximum number of non-attacking bishops that can be placed on a
1
0
1
x
1
0
1
chessboard.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
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 2 n − 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
2
n
−
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
2
n
−
1
bishops. However, if we had
2
n
−
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
2
n
−
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.
Log in to reply
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.
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.
http://mathworld.wolfram.com/BishopsProblem.html
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.
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.
Problem Loading...
Note Loading...
Set Loading...
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 = 1 0 1 and hence the maximum number of bishops possible is 2 ∗ 1 0 1 − 2 = 2 0 0 .