MathDB

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.

Problem Statement