Library / /85 of 397

, 2022

Combinatorics Difficulty 5.2 AIME, harder Prove it Taiwan

Let $m > 1$ be a positive integer. A mouse wants to jump from the bottom-left corner cell $a$ to the top-right corner cell $b$ of a $3m \times 3m$ chessboard. Each time, the mouse can move to the cell one square to the right or one square above its current position. However, some cells on the board have mouse traps placed on them; if the mouse runs onto a mouse trap, it becomes stuck and can no longer move.
For a set $X$ consisting of cells on the board, we say $X$ blocks the mouse if and only if, when traps are placed on all the cells of $X$ , the mouse cannot jump from $a$ to $b$ . We say $X$ is minimal if and only if $X$ blocks the mouse, but removing any cell of $X$ causes it to no longer block the mouse. Prove:
(i) The number of cells in any minimal set that blocks the mouse is not greater than $3m^2$ .
(ii) Prove that there exists a minimal set that blocks the mouse with no fewer than $3m^2 - 3m$ cells.

Solution

(a) For a minimal set $X$ , without touching $X$ , let $A$ be the set of all cells the mouse can reach from $a$ , and let $B$ be the set of all cells from which $b$ can be reached.
Note that from $A$ one can reach at most $2|A|$ cells (including $A$ and $X$ , excluding $a$ ), hence
$2|A| \geq |X| + (|A| - 1) \Leftrightarrow |X| \leq |A| + 1.$
Similarly, $|X| \leq |B| + 1$ , and thus $9m^2 \geq |A| + |B| + |X| \geq 3|m^2 - 2$ , that is, $|X| \leq 3m^2$ .

(b) Below is a minimal set with $3m^2 - 2m + 2$ cells:

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.