Problem

Source: Italy MO 2024 P5

Tags: combinatorics, combinatorics proposed



A fortress is a finite collection of cells in an infinite square grid with the property that one can pass from any cell of the fortress to any other by a sequence of moves to a cell with a common boundary line (but it can have "holes"). The walls of a fortress are the unit segments between cells belonging to the fortress and cells not belonging to the fortress. The area $A$ of a fortress is the number of cells it consists of. The perimeter $P$ is the total length of its walls. Each cell of the fortress can contain a guard which can oversee the cells to the top, the bottom, the right and the left of this cell, up until the next wall (it also oversees its own cell). (a) Determine the smallest integer $k$ such that $k$ guards suffice to oversee all cells of any fortress of perimeter $P \le 2024$. (b) Determine the smallest integer $k$ such that $k$ guards suffice to oversee all cells of any fortress of area $A \le 2024$.