Question 122
Let $n \geqslant 2$ be an integer. A frog moves on a grid of $3n \times 3n$ cells, each time jumping from a cell to the cell located just above it or just to its right. It wants to go from the bottom-left corner, marked $S$, to the top-right corner, marked $F$. Unfortunately, some cells are trapped, and if the frog jumps onto such a cell, it will remain stuck there.
A set of trapped cells is called blocking if it prevents the frog from going from cell $S$ to cell $F$. A blocking set is also called minimal if, as soon as the trap is removed from any one of the cells of this set, the set is no longer blocking.
For example, the black cells of the grid below form a minimal blocking set.
a) Prove that there exists a minimal blocking set containing at least $3n(n-1)$ cells.
b) Prove that every minimal blocking set contains at most $3n^{2}$ cells.
A set of trapped cells is called blocking if it prevents the frog from going from cell $S$ to cell $F$. A blocking set is also called minimal if, as soon as the trap is removed from any one of the cells of this set, the set is no longer blocking.
For example, the black cells of the grid below form a minimal blocking set.
a) Prove that there exists a minimal blocking set containing at least $3n(n-1)$ cells.
b) Prove that every minimal blocking set contains at most $3n^{2}$ cells.