BMO 2022 shortlist

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 in either side of the corresponding edge have different colours. 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 $4N-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 $4N=(4N-4)+4\le (n+1{)}^2$. Thus $N\le \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,\dots ,2m\}$ in the cells and colouring red all cells both of whose coordinates are even, and blue all other cells. An example for $n=9$ is shown below.