ISL 2021 C7

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$.