Q4 Matemática  (Balkan MO 2022)

Considere uma grade $n\times n$ consistindo de $n^2$ até células, onde $n\ge 3$ é um dado inteiro positivo ímpar. Primeiro, Dionísio colore cada célula de vermelho ou azul. Sabe-se que um sapo pode pular de uma célula para outra se e somente se essas células tiverem a mesma cor e compartilharem pelo menos um vértice. Então, Xanthias visualiza a coloração e em seguida coloca $k$ sapos nas células para que cada uma das células $n^2$ possa ser alcançada por um sapo em um número finito (possível zero) de saltos. Encontre o menor valor de $k$ para o qual isso seja sempre possível, independentemente da coloração escolhida por Dionísio. Proposto por Tommy Walker Mackay, Reino Unido