Балканская олимпиада по математике 2022 года | Казахстанские олимпиады

Рассмотрим таблицу $n\times n$, состоящую из $n^2$ единичных клеток, где $n \ge 3$ является заданным нечетным положительным целым числом. Сначала, Дионис окрашивает каждую клетку либо в красный, либо в синий цвет. Известно, что лягушка может прыгать из одной клетки в другую тогда и только тогда, когда эти клетки покрашены в одинаковый цвет и имеют хотя бы одну общую вершину. Затем Ксантиас видит раскраску и после этого размещает $k$ лягушек на некоторых клетках так, чтобы каждая из $n^2$ клеток могла быть достигнута лягушкой за конечное число (возможно, ноль) прыжков. Найдите наименьшее значение $k$, при котором это всегда возможно, независимо от раскраски, выбранной Дионисом.