Problem 1880

a.
In the following example the square is divided into $m$ stripes of size $3 \times 3m$. It is easy to see that $X$ is a minimal blocking set. The first and the last stripe each contains $3m-1$ cells from the set $X$; every other stripe contains $3m-2$ cells, see Figure 1. The total number of cells in the set $X$ is $3m^{2} - 2m + 2$.

b.
Solution 1.
For a given blocking set $X$, say that a non-sticky cell is red if the frog can reach it from $S$ via some hops without entering set $X$. We call a non-sticky cell blue if the frog can reach $F$ from that cell via hops without entering set $X$. One can regard the blue cells as those reachable from $F$ by anti-hops, i.e. moves downwards and to the left. We also colour all cells in $X$ green. It follows from the definition of the blocking set that no cell will be coloured twice. In Figure 2 we show a sample of a blocking set and the corresponding colouring.

Now assume that $X$ is a minimal blocking set. We denote by $R$ (resp., $B$ and $G$) the total number of red (resp., blue and green) cells.

We claim that $G \leqslant R+1$ and $G \leqslant B+1$. Indeed, there are at most $2R$ possible frog hops from red cells. Every green or red cell (except for $S$) is accessible by such hops. Hence $2R \geqslant G + (R-1)$, or equivalently $G \leqslant R+1$. In order to prove the inequality $G \leqslant B+1$, we turn over the board and apply the similar arguments.

Therefore we get $9m^{2} \geqslant B+R+G \geqslant 3G-2$, so $G \leqslant 3m^{2}$.

Solution 2.
We shall use the same colouring as in the above solution. Again, assume that $X$ is a minimal blocking set.

Note that any $2 \times 2$ square cannot contain more than 2 green cells. Indeed, on Figure 3(a) the cell marked with "?" does not block any path, while on Figure 3(b) the cell marked with "?" should be coloured red and blue simultaneously. So we can split all green cells into chains consisting of three types of links shown on Figure 4 (diagonal link in the other direction is not allowed, corresponding green cells must belong to different chains). For example, there are 3 chains in Figure 2(b).

(a)

(b)

Figure 3

Figure 4

Figure 5

We will inscribe green chains in disjoint axis-aligned rectangles so that the number of green cells in each rectangle will not exceed $1/3$ of the area of the rectangle. This will give us the bound $G \leqslant 3m^{2}$. Sometimes the rectangle will be the minimal bounding rectangle of the chain, sometimes minimal bounding rectangles will be expanded in one or two directions in order to have sufficiently large area.

Note that for any two consecutive cells in the chain the colouring of some neighbouring cells is uniquely defined (see Figure 5). In particular, this observation gives a corresponding rectangle for the chains of height (or width) 1 (see Figure 6(a)). A separate green cell can be inscribed in $1 \times 3$ or $3 \times 1$ rectangle with one red and one blue cell, see Figure 6(b)-(c), otherwise we get one of impossible configurations shown in Figure 3.

Figure 6
Figure 7

Any diagonal chain of length 2 is always inscribed in a $2 \times 3$ or $3 \times 2$ rectangle without another green cells. Indeed, one of the squares marked with "?" in Figure 7(a) must be red. If it is the bottom question mark, then the remaining cell in the corresponding $2 \times 3$ rectangle must have the same colour, see Figure 7(b).

A longer chain of height (or width) 2 always has a horizontal (resp., vertical) link and can be inscribed into a $3 \times a$ rectangle. In this case we expand the minimal bounding rectangle across the long side which touches the mentioned link. On Figure 8(a) the corresponding expansion of the minimal bounding rectangle is coloured in light blue. The upper right corner cell must be also blue. Indeed it cannot be red or green. If it is not coloured in blue, see Figure 8(b), then all anti-hop paths from $F$ to "?" are blocked with green cells. And these green cells are surrounded by blue ones, what is impossible. In this case the green chain contains $a$ cells, which is exactly $1/3$ of the area of the rectangle.

In the remaining case the minimal bounding rectangle of the chain is of size $a \times b$ where $a, b \geqslant 3$. Denote by $\ell$ the length of the chain (i.e. the number of cells in the chain).

If the chain has at least two diagonal links (see Figure 9), then $\ell \leqslant a+b-3 \leqslant ab/3$.

If the chain has only one diagonal link then $\ell = a+b-2$. In this case the chain has horizontal and vertical end-links, and we expand the minimal bounding rectangle in two directions to get an $(a+1) \times (b+1)$ rectangle. On Figure 10 a corresponding expansion of the minimal bounding rectangle is coloured in light red. Again the length of the chain does not exceed $1/3$ of the rectangle's area: $\ell \leqslant a+b-2 \leqslant (a+1)(b+1)/3$.

On the next step we will use the following statement: all cells in constructed rectangles are coloured red, green or blue (the cells upwards and to the right of green cells are blue; the cells downwards and to the left of green cells are red). The proof repeats the same arguments as before (see Figure 8(b).)

Figure 9

Figure 10

Figure 11

Note that all constructed rectangles are disjoint. Indeed, assume that two rectangles have a common cell. Using the above statement, one can see that the only such cell can be a common corner cell, as shown in Figure 11. Moreover, in this case both rectangles should be expanded, otherwise they would share a green corner cell.

If they were expanded along the same axis (see Figure 11(a)), then again the common corner cannot be coloured correctly. If they were expanded along different axes (see Figure 11(b)) then the two chains have a common point and must be connected in one chain. (These arguments work for $2 \times 3$ and $1 \times 3$ rectangles in a similar manner.)