MathDB

Place eight rooks on a standard

8 \times 8

chessboard so that no two are in the same row or column. With the standard rules of chess, this means that no two rooks are attacking each other. Now paint

27

of the remaining squares (not currently occupied by rooks) red. Prove that no matter how the rooks are arranged and which set of

27

squares are painted, it is always possible to move some or all of the rooks so that:
• All the rooks are still on unpainted squares. • The rooks are still not attacking each other (no two are in the same row or same column). • At least one formerly empty square now has a rook on it; that is, the rooks are not on the same

8

squares as before.

Problem Statement