Placing few guards in a fortress to oversee everything
Source: Italy MO 2024 P5
May 15, 2024
combinatoricscombinatorics proposed
Problem Statement
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 of a fortress is the number of cells it consists of. The perimeter 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 such that guards suffice to oversee all cells of any fortress of perimeter .
(b) Determine the smallest integer such that guards suffice to oversee all cells of any fortress of area .