MathDB

12

Part of 2022 IOQM India

Problems(1)

IOQM 2022 P12

Source:

3/8/2022
A 12×1212 \times 12 board is divided into 144144 unit squares by drawing lines parallel to the sides. Two rooks placed on two unit squares are said to be non-attacking if they are not in the same column or same row. Find the least number NN such that if NN rooks are placed on the unit squares, one rook per square, we can always find 77 rooks such that no two are attacking each other.
combinatoricsIOQM