Problem

Source: Czech-Polish-Slovak Match Junior 2019, team p2 CPSJ

Tags: combinatorics



The chess piece sick rook can move along rows and columns as a regular rook, but at most by $2$ fields. We can place sick rooks on a square board in such a way that no two of them attack each other and no field is attacked by more than one sick rook. a) Prove that on $30\times 30$ board, we cannot place more than $100$ sick rooks. b) Find the maximum number of sick rooks which can be placed on $8\times 8$ board. c) Prove that on $32\times 32$ board, we cannot place more than $120$ sick rooks.