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.
Problem
Source: MEMO 2023 T3
Tags: combinatorics
ThisIsReserved
28.08.2023 12:08
Nice one. The answer is $b=41.$ We will prove that among $41$ green squares, there always exists $7,$ among whitch no two lies on the same diagonal, but this is not the case for $40.$ To see, why $40$ green squares are not enough, consider the first diagram, where the green squares can be partitioed into $6$ diagonals (the main diagonals an the diagonals adjacent to it), so if one chooses seven green squares two of them lies on the same diagonal. Now we'll prove that among $41$ green squares, there is always $7,$ no two lying in the same diagonal. For this reason, consider the second picture, where among the squares, colored by the same color no two lies in the same diagonal (this is a direct checking). Hence there are at most $4$ green squares which are not colored, and among the other $37$ (or more), there are at least $7$ with the same color, and this $7$ squares satisfy the conditions.
Attachments:
