IPSC Logo

Internet Problem Solving Contest

IPSC 2004

Solution to Problem B – Bishops

This was probably the easiest task. Let's call a diagonal from top-left to bottom-right a "TLBD" diagonal and a diagonal from bottom-left to top-right a "BLTR" diagonal.

On a chessboard of size N × N there are 2N-1 "TLBD" diagonals. On each of them we can place at most one bishop. Therefore the chessboard can contain at most 2N-1 bishops. In fact, it is impossible to place 2N-1 bishops, because in such case we would have to place a bishop on every "TLBD" diagonal, including the top-right and bottom-left corner of the chessboard. But these two bishops threaten each other. Therefore we can place at most 2N-2 bishops on the chessboard.

It is indeed possible to place 2N-2 bishops on the chessboard. For example, one can use all places in the bottom row and the top row of the chessboard except the two right corners.

There is one special case N=1. In that case, the top-right and bottom-left corner are the same place. The maximal number of bishops for N=1 is clearly 1.