Question 39
Let $n \ge 3$ be an odd positive integer, and consider an $n \times n$ grid containing $n^2$ cells. Dionysus colours each cell either red or blue. A frog can hop directly between two cells if they have the same colour and share at least one vertex. Xanthias views the colouring, and wants to place frogs on $k$ of the cells so that any cell can be reached by a frog in a finite number of hops. Find the least value of $k$ such that Xanthias can always be successful regardless of the colouring chosen by Dionysus.