## T-3

Find the smallest integer $b$ with the following property: For each way of colouring exactly $b$ squares of an $8 \times 8$ chessboard green, one can place 7 bishops on 7 green squares so that no two bishops attack each other.

Remark. Two bishops attack each other if they are on the same diagonal.

Answer. 41


Solution. Let us place 40 bishops on 6 diagonals as shown in Figure 2. If we select any 7 of the placed bishops, by Pigeon hole principle, at least two of the selected bishops are on the same diagonal, so they attack each other. Thus, the number $b$ of selected bishops is at least 41.

![](https://cdn.mathpix.com/cropped/2024_06_05_775ea5fd909fa7632c76g-14.jpg?height=437&width=443&top_left_y=1095&top_left_x=812)

Figure 1

Now, suppose for a contrary, that there is a placement of 41 bishops such there are not 7 non-attacking bishops. Divide all tiles to 8 groups as shown in Figure ??. It is easy to see that any two bishops belonging to the same group do not attack each other. Therefore, each group contains at most 6 bishops. Moreover, groups 7 and 8 contain at most 2 bishops due to their size. Therefore, we have at most $6 \cdot 6+2 \cdot 2=40$ bishops, which is a contradiction. Therefore, from any placement of 41 bishops, it is possible to select some 7 of them such that no two attack each other. This, together with the lower bound of $b \geq 41$ finishes this solution.

![](https://cdn.mathpix.com/cropped/2024_06_05_775ea5fd909fa7632c76g-14.jpg?height=429&width=422&top_left_y=2127&top_left_x=817)

Figure 2

Comment (1). A weaker upper bound of 49 can be shown as follows: Consider a placement of 49. bishops. We have 8 rows and $49 / 8>6$, so by Pigeon hole principle, there is a row with at least 7 bishops. Clearly, bishops in the same row do not attack each other.

Comment (2). This problem can be generalised for larger dimensions of the chessboard and also larger number of sought non-attacking bishops.

