BALKAN 2022 Problem 4

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.