Question 93
Let $m \gt 1$ be a positive integer. A mouse wants to go from the bottom-left cell $a$ to the top-right cell $b$ of a $3m \times 3m$ chessboard. In each move the mouse can run to the cell directly to the right of it or directly above it. However, some cells of the board contain glue traps; if the mouse runs onto a glue trap it gets stuck and cannot move any more.
For a set $X$ of cells of the board, we say that $X$ blocks the mouse if and only if, when all cells of $X$ contain glue traps, the mouse cannot get from $a$ to $b$. We say that $X$ is minimal if and only if $X$ blocks the mouse, but after removing any one cell from $X$ it no longer blocks the mouse. Prove that:
(i) every minimal set blocking the mouse has at most $3m^2$ cells;
(ii) there exists a minimal set blocking the mouse with at least $3m^2 - 3m$ cells.
For a set $X$ of cells of the board, we say that $X$ blocks the mouse if and only if, when all cells of $X$ contain glue traps, the mouse cannot get from $a$ to $b$. We say that $X$ is minimal if and only if $X$ blocks the mouse, but after removing any one cell from $X$ it no longer blocks the mouse. Prove that:
(i) every minimal set blocking the mouse has at most $3m^2$ cells;
(ii) there exists a minimal set blocking the mouse with at least $3m^2 - 3m$ cells.