69th Belarusian Mathematical Olympiad

First solution. We will prove the statement of the problem in the general case of rectangular boards $n\times m$. Suppose in contrary that there exist such positive integers $n$ and $m$ and a movement of beetles, that none of the beetles crawled into the center of the cell at the vertex of which it initially sat. Take such a pair $(n,m)$ with minimal $n+m$. Clearly, for $1\times 1$ board the statement of the problem is true, so without loss of generality assume that $n\ge 2$.

Enumerate the columns from left to right by numbers $1,\dots ,m$ and the vertical gridlines by numbers $0,\dots ,m$. Similarly, enumerate the rows from top to bottom by numbers $1,\dots ,n$ and the horizontal gridlines by numbers $0,\dots ,n$. So, $(i,j)$-cell have $(i-1,j-1),(i-1,j),(i,j)$ and $(i,j-1)$ vertices.

Suppose that for some $i$, $1\le i\le m-1$, the beetle crawled from $(2,i-1)$-node to the center of $(1,i)$-cell. Then the beetle from $(1,i-1)$-node couldn't move to the centers of $(1,i-1)$ and $(2,i)$ cells, so it crawled to the center of $(1,i+1)$-cell. Hence the beetle from $(1,i)$-node crawled to the center of $(1,i+2)$-node. Similarly, the beetle from the $(1,j)$-node, $i<j<m-1$, crawled to the center of $(1,j+2)$-cell. Finally, for the beetle from $(1,m-1)$-node we obtain a contradiction, since it had to move to the center of the cell, adjacent to $(1,m)$-cell: either $(1,m-1)$-cell or $(2,m)$-cell, both having $(1,m-1)$-node as a vertex. If we now suppose that the beetle from $(2,i-1)$-node, $2\le i\le m$, moved to the center of $(1,i-1)$-cell, we obtain a contradiction in a similar way.

Consider the next transformation of the $n\times m$ board. Remove the first row and all beetles from the top (0-th) gridline. For each of the remaining beetles, which crawled to the first row, let it now crawl one row below. And for the rest of the beetles don't change anything. It is easy to see that after transformation we obtain a counterexample on to the statement of the problem on the $(n-1,m)$ board. But this contradicts the minimality of $n+m$. Therefore, our assumption of the existence of a counterexample is false.

Second solution. By a distance between a beetle and a cell call the minimal number of unit moves along the gridlines, which this beetle require to get to the vertex of the cell. The distance between the beetle $\mathfrak{K}$ and the cell $C^{\mathfrak{K}}$, at which it crawled, call its path.

We are to prove that there exists a beetle with zero path. Suppose a contrary and choose the beetle ${\mathfrak{K}}_1$ with minimal path. The gridlines, passing through the starting vertex of ${\mathfrak{K}}_1$ divide the board into four rectangles. Without loss of generality let $C^{{\mathfrak{K}}_1}$ lie in the top right rectangle. Since the path of ${\mathfrak{K}}_1$ is positive, we may assume that $C^{{\mathfrak{K}}_1}$ is not located on the left border of the rectangle.

Consider the beetle ${\mathfrak{K}}_2$, which sat to the right of ${\mathfrak{K}}_1$. It crawled to $C^{{\mathfrak{K}}_1}$ or to the adjacent to it. But the distance between ${\mathfrak{K}}_2$ and $C^{{\mathfrak{K}}_1}$ is less than the path of ${\mathfrak{K}}_1$, and the same hold for the left and bottom adjacent cells of $C^{{\mathfrak{K}}_1}$. Hence $C^{{\mathfrak{K}}_2}$ is located to the right or top of $C^{{\mathfrak{K}}_1}$ and the next condition hold: (1) the path of ${\mathfrak{K}}_2$ equals to the path of ${\mathfrak{K}}_1$, i.e. it is minimal; and (2) $C^{{\mathfrak{K}}_2}$ lies in the top right rectangle, with respect to ${\mathfrak{K}}_2$.

Replacing the beetle ${\mathfrak{K}}_1$ with ${\mathfrak{K}}_2$ we find the beetle ${\mathfrak{K}}_3$ satisfying the conditions (1) and (2). Continue this considerations, we obtain the sequence of beetles, each satisfying (1) and (2), such that the distance from the beetles to the top right cell of the board is decreasing at each step. It is evident that at some moment we get a contradiction.