Problem. Consider an $n \times n$ grid consisting of $n^{2}$ unit cells, where $n \geqslant 3$ is a given odd positive integer. First, Dionysus colours each cell either red or blue. It is known that a frog can hop from one cell to another if and only if these cells have the same colour and share at least one vertex. Then, Xanthias views the colouring and next places $k$ frogs on the cells so that each of the $n^{2}$ cells can be reached by a frog in a finite number (possibly zero) of hops. Find the least value of $k$ for which this is always possible regardless of the colouring chosen by Dionysus.

Note. Dionysus and Xanthias are characters from the play of Aristophanes 'frogs'. Dionysus is the known god of wine and Xanthias is his witty slave.
. Let $G$ be the graph whose vertices are all $(n+1)^{2}$ vertices of the grid and where two vertices are adjacent if and only if they are adjacent in the grid and moreover the two cells on either side of the corresponding edge have different colors.

The connected components of $G$, excluding the isolated vertices, are precisely the boundaries between pairs of monochromatic regions each of which can be covered by a single frog. Each time we add one of these components in the grid, it creates exactly one new monochromatic region. So the number of frogs required is one more than the number of such components of $G$.

It is easy to check that every corner vertex of the grid has degree 0, every boundary vertex of the grid has degree 0 or 1, and every 'internal' vertex of the grid has degree 0, 2, or 4. It is also easy to see that every component of $G$ which is not an isolated vertex must contain at least four vertices unless it is the boundary of a single corner of the grid, in which case it contains only three vertices.

Writing $N$ for the number of components which are not isolated vertices, we see that in total they contain at least $4 N - 4$ vertices. (As at most four of them contain 3 vertices and all others contain 4 vertices.) Since we also have at least 4 components which are isolated vertices, then $4 N = (4 N - 4) + 4 \leq (n+1)^{2}$. Thus $N \leq \frac{(n+1)^{2}}{4}$ and therefore the minimal number of frogs required is $\frac{(n+1)^{2}}{4} + 1$.

This bound for $n = 2m + 1$ is achieved by putting coordinates $(x, y)$ with $x, y \in \{0, 1, \ldots, 2m\}$ in the cells and coloring red all cells both of whose coordinates are even, and blue all other cells. An example for $n = 9$ is shown above.

![](https://cdn.mathpix.com/cropped/2024_12_10_b5da7837303016ab5616g-6.jpg?height=446&width=448&top_left_y=2013&top_left_x=833)