The plan of a picture gallery is a chequered figure where each square is a room, and every room can be reached from each other by moving to rooms adjacent by side. A custodian in a room can watch all the rooms that can be reached from this room by one move of a chess rook (without leaving the gallery). What minimum number of custodians is sufficient to watch all the rooms in every gallery of $n$ rooms ($n > 1$)?
Problem
Source: Tuymaada Olympiad 2019 junior p3
Tags: combinatorics, minimum value, minimum, Chessboard
M11100111001Y1R
02.07.2023 01:02
First we show that every polyomino with $n$ tiles can be guarded by $\lfloor \frac{n}{2} \rfloor$ rooks. We $2–color$ the polyomino according to the parity of the sum of coordinates of each tile; that is, tiles that share a side get opposite colors. We take the color with the smaller number of tiles, and place rooks on all tiles of that color, so that there are at most $\lfloor \frac{n}{2} \rfloor$ rooks. Because the interior of the polyomino is connected, every tile shares a side with some other tile. Thus every tile is guarded by at least one of the rooks. Next we exhibit, for every positive integer $n,$ a polyomino with n tiles such that the minimum number of rooks needed to guard it is $\lfloor \frac{n}{2} \rfloor.$ The construction, shown in Figure $1$ for $n = 10$ and $n = 11$ tiles, consists of one center column with individual tiles attached on either side, alternating between left and right. This construction generates a polyomino for even $n = 2m.$ For an odd number $n = 2m+1$ we construct a polyomino by placing a tile on the bottom-most part of center column of polyomino with $n-1$ tiles. To prove that $\lfloor \frac{n}{2} \rfloor$ rook guards are needed, we observe that there are exactly $\lfloor \frac{n}{2} \rfloor$ tiles not in the center column, and that no two of these can be guarded by the same rook.