2021 IMO Shortlist 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$.

考虑一个方格 $3 m \times 3 m$ 正方形，其中 $m$ 是大于 1 的整数。一只青蛙坐在左下角单元格 $S$ 上，想要到达右上角单元格 $F$。青蛙可以从任何单元格跳到右侧的下一个单元格或向上的下一个单元格。有些细胞可能有粘性，青蛙一旦跳到这样的细胞上就会被困住。如果当 $X$ 的所有单元格都具有粘性时，青蛙无法从 $S$ 到达 $F$，则一组 $X$ 单元格被称为阻塞。如果阻塞集不包含更小的阻塞集，则该阻塞集是最小的。 (a) 证明存在包含至少 $3 m^{2}-3 m$ 个单元的最小阻塞集。 (b) 证明每个最小分块集最多包含 $3 m^{2}$ 个单元。笔记。 $m=2$ 的最小阻塞集示例如下所示。 $X$ 集合的单元格由字母 $x$ 标记。