Olympiad workbookIOQMPermutation and Combination
A 12 12 board is divided into 144 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 N such that if N rooks are placed on the unit square, one rook per square, we can always find 7 rooks such that no that no two are attacking each other.
Correct answer
73
Step-by-step solution
Clearly maximum 12 rooks can be placed in non attacking as each rooks will cover one row and one column 7 rooks in non-attacking position mean 7 horizontal and 7 vertical gets occupied If we start placing rooks 12 6+1=73 If we place 73 rooks Then are will always final 7 rooks in non-attacking position