Question 15
Consider a checkered $3 m \times 3 m$ square, where $m$ is an integer greater than 1. A frog sits on the lower left corner cell $S$ and wants to get to the upper right corner cell $F$. The frog can hop from any cell to either the next cell to the right or the next cell upwards.
Some cells can be sticky, and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called blocking if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is minimal if it does not contain a smaller blocking set.
(a) Prove that there exists a minimal blocking set containing at least $3 m^{2}-3 m$ cells.
(b) Prove that every minimal blocking set contains at most $3 m^{2}$ cells.
Note. An example of a minimal blocking set for $m=2$ is shown below. Cells of the set $X$ are marked by letters $x$.
| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |
Original illustration of the example:
Some cells can be sticky, and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called blocking if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is minimal if it does not contain a smaller blocking set.
(a) Prove that there exists a minimal blocking set containing at least $3 m^{2}-3 m$ cells.
(b) Prove that every minimal blocking set contains at most $3 m^{2}$ cells.
Note. An example of a minimal blocking set for $m=2$ is shown below. Cells of the set $X$ are marked by letters $x$.
| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |
Original illustration of the example: