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$.
Problem
Source: Italy MO 2024 P5
Tags: combinatorics, combinatorics proposed
16.05.2024 13:00
(a) In a $506\times 506$ square with less than $506$ guards there exist a row and a column with no guards and their intersection is not overseen, so $k\ge 506$. We will show that $506$ guards are enough. The construction is just to keep adding guards in squares that are not overseen. For each guard we add we mark the $4$ walls that are to the left, to the right, above and below his position. Note that they can't have already been marked because otherwise the cell in which we are placing the guard would be aligned with another guard and would be already overseen. So after $P/4\le 506$ moves all the walls will be marked and the process will have ended. Therefore the answer is $\boxed{506}$. (b) Consider the fortress attached (with area $2024$). Each cell in the first and third row must be overseen by a different guard, so at least $1012$ guards are required. To show that $1012$ guards are enough, color the grid like a chessboard and suppose there are more white squares than black squares in the fortress. Place at most $A/2\le 1012$ guards on all black squares. Then all the black squares are overseen. Every white square in the fortress borders another square, which must be black, so all white squares are also overseen. Therefore the answer is $\boxed{1012}$.
Attachments:
