39-я Балканская математическая олимпиада. Кипр, 2022 год

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

Комментарий/решение

Пусть Дионис покрасил таблицу окошками(синих меньше) тогда очевидно для каждой синей нужна одна клетка потому что никакая синяя не имеет общей вершины с другой. Также для всех красных достаточно всего одна лягушка. нужно не менее $(\frac{n+1}{2})^2+1$ лягушек. Такое кол-во всегда хватает покажем это. Для произвольной раскраски рассмотрим вершины решётки их $(n+1)^2$. Соединим две соседние вершины ребром, если по разные стороны от соответствующего ребра лежат клетки разных цветов. Таким образом, получаем набор границ между одноцветными областями. Каждая лягушка покрывает одну одноцветную область. Число таких областей равно числу границ между цветами плюс 1. Каждая граница проходит по линиям решётки и содержит не менее 4 узлов, за исключением не более чем четырёх угловых границ, содержащих по 3 узла. Поскольку всего узлов $(n+1)^2$ число границ не превосходит $\frac{(n+1)^2}{4}$

Следовательно, минимальное число лягушек которых заведомо хватит равно $(\frac{n+1}{2})^2+1$. Тривиальная идея.