I feel like I can prove that part (b) is false - are you sure it's not that there's no minimal blocking set of more than $3m^2$ cells, say? (A statement there exists a relatively slick proof of)

At least in my country's TST, the wording for part (b) is (b) Prove that every minimal blocking set contains at most $3m^2$ cells.

Yeah, @above and @2above, you are right. I made a slight typo, but it’s fixed now, thanks for pointing it out

oVlad wrote: Consider a checkered $3m\times 3m$ 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. Prove that there exists a minimal blocking set containing at least $3m^2-3m$ cells. Prove that every minimal blocking set containing at most $3m^2$ cells. a) There exists a construction with $3m^2-2m$ cells. Here is a demonstration for the case $m=3$ . [asy][asy] unitsize(16); int m = 3; for(int i=1; i <= 3*m - 2; i=i+3) { fill((i,2)--(i+1,2)--(i+1,3*m - 2)--(i,3*m - 2)--cycle,grey); fill((i+1,1)--(i+2,1)--(i+2,2)--(i+1,2)--cycle,grey); fill((i-1,3*m-2)--(i,3*m-2)--(i,3*m - 1)--(i-1,3*m - 1)--cycle,grey); } for(int i=0; i <= 3*m; ++i) { if(i%3==0) { draw((i,0)--(i,3*m),linewidth(1.5)); draw((0,i)--(3*m,i),linewidth(1.5)); } else { draw((i,0)--(i,3*m)); draw((0,i)--(3*m,i)); } } [/asy][/asy] b) Let $A$ be the collection of cells that can be reached from $S$ by a finite sequence of moves. Similarly, let $B$ be the collection of cells such that $F$ can be reached from them by a finite sequence of moves. Then $A\cup B\cup X$ is a partition of the square since $X$ is a minimal blocking set. Now, let $T$ be the number of ordered pairs $(u,v)$ such that $u\in A$ and $v$ is a neighbor of $u$ to the right or upwards. Since $X$ is a minimal blocking set, then every member of $X$ is a right component of at least one pair. Moreover, every element of $A$ except $S$ is a right component of at least one pair, so $T\ge |X|+|A|-1$. Every cell of $A$ can be a left component at most twice so $T\le 2|A|$. Hence $|X|\le |A|+1$. From symmetry we obtain $|X|\le |B|+1$ so $$3|X|\le |X|+(|A|+1)+(|B|+1)=9m^2+2.$$Therefore $|X|\le\left\lfloor\frac{9m^2+2}{3}\right\rfloor=3m^2$.

i feel bad for the frog

Same as @2above more or less... Part a Initial attempt at coloring for $m = 3$ cells, this idea is simple: divide into equal sized $3\times3m$ size strips and partition accordingly; this is a config for $3m^2-2m+2$, but if we delete the cells marked as an X and color the cells marked as an O, we get a further minimal coloring of $3m^2-2m$, thereby proving the construction Part b This is the fun stuff. We develop the following coloring pattern: Call the region of accessibility from the bottom left corner the group of $|R|$ cells and color appropriately. All cells that are reachable from this bottom left corner will be colored red, while all cells that are accessible from top right corner via a sequence of reversed hops (left and down) be colored blue, belonging to the partition of size $|B|$. The remaining cells will be colored yellow and would be members in the partition of size $|X|$. It is easy to see that $X \cup R \cup B$ forms the partition of the grid itself and hence, $|X| + |R| + |B| \leq 9m^2$. An example coloring is shown below: Now assume $X$ is minimal. If this be the case, then we have the following 2 things: Claim 1: $|X| \leq |R| + 1$ Proof: If we denote $A$ as the set of cells that the frog can access starting on a red cell, on any given step, we have that $A$ can be thought of in two components: $(p, q)$, where all $p \in R$ and $q$ is accessible from cell $p$ either via a hop up or a hop to the right. This means that because $X$ is minimal, there exists at least one pair of cells $(p, q) \in A$ such that every cell in $X$ is the $q$ parameter of this given pair. Except for the starting square, we have that every element in $R$ forms the right component of at least one pair, and so we know that $|A| \geq |X| + |R| - 1$ and that every cell in $|R|$ can be expressed as the parameter $p$ at most twice, and so because of this, $|A| \leq 2|R| \implies |X| \leq |R| + 1 \blacksquare$ Claim 2: $|X| \leq |B| + 1$ Proof: Like a nice slice of meat that has been cooked on one side, flip the square around. Symmetry takes care of the rest $\blacksquare$ Hence, $3|X| \leq |X| + \left(|R| + 1\right) + \left(|B| + 1\right) \implies \left(|X| + |R| + |B|\right) \in \left[3\left|X\right|-2,9m^2\right] \implies |X|\le\left\lfloor\frac{9m^2+2}{3}\right\rfloor=\color{red}\boxed{3m^2}$ as asked $\blacksquare$

Color red all cells, reachable from $S$ without entering $X;$ color green cells of $X,$ and color blue all cells, from which can be reached $F$ without entering $X.$ (a.) We present the example of minimal blocking set with $3m^2-2m+2$ cells colored green (for the case $m=3$): [asy][asy] unitsize(12); int s = 3; fill((0,0)--(0,8)--(1,8)--(1,2)--(2,2)--(2,1)--(3,1)--(3,7)--(4,7)--(4,2)--(5,2)--(5,1)--(6,1)--(6,7)--(7,7)--(7,1)--(8,1)--(8,0)--cycle, red); fill((9,9)--(9,1)--(8,1)--(8,7)--(7,7)--(7,8)--(6,8)--(6,2)--(5,2)--(5,7)--(4,7)--(4,8)--(3,8)--(3,2)--(2,2)--(2,8)--(1,8)--(1,9)--cycle, blue); fill((3,1)--(3,2)--(2,2)--(2,8)--(1,8)--(1,9)--(0,9)--(0,8)--(1,8)--(1,2)--(2,2)--(2,1)--cycle, green); fill((6,1)--(6,2)--(5,2)--(5,7)--(4,7)--(4,8)--(3,8)--(3,7)--(4,7)--(4,2)--(5,2)--(5,1)--cycle, green); fill((9,0)--(9,1)--(8,1)--(8,7)--(7,7)--(7,8)--(6,8)--(6,7)--(7,7)--(7,1)--(8,1)--(8,0)--cycle, green); label("$S$", (0.5, 0.5)); label("$F$", (8.5, 8.5)); for(int i=0; i <= 3*s; ++i) { if(i%3==0) { draw((i,0)--(i,3*s),linewidth(1.5)); draw((0,i)--(3*s,i),linewidth(1.5)); } else { draw((i,0)--(i,3*s)); draw((0,i)--(3*s,i)); } } [/asy][/asy] (b.) Denote by $r,g,b$ numbers of red, green and blue cells respectively; since set is blocking, none of cell painted two colors. Notice that there are at most $2r$ hops which frog can perform from red cell, and all red and green cells except $S$ are reachable with such hops, therefore $(r-1)+g\leq 2r\implies g\leq r+1.$ By symmetric arguments $g\leq b+1,$ thus we have $$3g-2\leq r+g+b\leq 9m^2\implies g\leq 3m^2\text{ } \blacksquare$$

Just got this problem, and here's some remarks as per my experimentation. (a) My construction for (a) is similar except I didn't optimize for the first and the last $3\times 3m$ strip (so all the $3\times 3m$ strips have the same blocking sets), resulting in a suboptimal bound $3m^2-2m$ instead. It's motivated by mazes (roughly, "just break a wall and you're free").

lol.

For part (a) use the same construction in post #5. For part (b), replace sticky cells with impenetrable walls. Take a minimal blocking set and color it black. Color every cell reachable from $S$ blue and every cell from which $F$ is reachable red, so each cell should be colored with at most one of these three colors. For any blue cell, the cells directly to the right and above should either be blue or black. Furthermore, if some cell in the blocking set isn't above or to the right of any blue cells, we can delete it and the set is still blocking; the same is true if it's not below or to the left of to any red cells. Finally, the sets of red and blue cells are (individually) connected. Now, I claim that if we have $n$ blue cells, there are at most $n+1$ non-blue cells either directly above or to the right of a blue cell. This is by induction with $n=1$ trivial, adding a blue cell $b$ in a place where there aren't blue cells which are both at least as high and as least as right as $b$. This then creates at most $2$ additional non-blue cells: the cells directly above and to the right of $b$. However, since our blue cells are connected, the spot where $b$ is added must have previously been a non-blue cell directly above or to the right of a blue cell, so we gain at most $1$ additional blue cell. This claim alternatively implies that if we have $N$ black cells, then we have at least $N-1$ blue cells. Furthermore, by rotating the diagram $180^\circ$, we also have at least $N-1$ red cells. Hence if this minimal blocking set has at least $3m^2+1$ cells then we need at least $9m^2+1$ cells in the grid, which is absurd. $\blacksquare$