Есть доска 15 на девять Мотя красит каждую клетку в один из трёх цветов это белый красный или синий когда Мотя закончит Вова может найти любую одноцветную пару клеток имеющих общую сторону и вершину и перекрасить эту пару клеток в зелёный цвет и так делать до тех пор пока это возможно мотя платит вове по пять рублей за каждую зелёную клетку сколько денег может гарантированно получить Вова?

Рассмотрим доску размером 15 на 9, то есть всего на ней 135 клеток. Мотя использует три цвета: белый, красный и синий.

Когда Вова перекрашивает пару соседних клеток в зелёный цвет, он получает 5 рублей за каждую перекрашенную клетку. Таким образом, за одну пару клеток Вова будет получать 10 рублей.

Давайте проанализируем, сколько пар клеток может быть перекрашено в зелёный цвет. Поскольку у Моти три цвета, он может раскрасить клетки так, что некоторые клетки будут однородными.

Чтобы Мотя гарантированно сначала использовал только один цвет, можно представить, что клеток каждого из трёх цветов на доске примерно поровну. В этом случае, если, например, 45 клеток будут одного цвета, а остальные 90 клеток поделены между двумя другими цветами (примерно по 45 клеток), то Вова сможет перекрашивать только те пары, которые находятся в одном цвете.

Для максимизации количества пар клеток на одной цветовой клетке, рассмотрим оптимальный способ раскраски. Пусть висит непривязанный метод "чередования" цветов, когда соседние клетки будут иметь разные цвета. Используем шахматный способ раскраски для двух цветов на доске, и третий цвет используем для разброса.

В этом случае, исходя из структуры доски, в идеальных условиях (максимальная возможность создания пар) мы должны достигнуть баланса, чтобы каждую цветовую пару можно было перекрасить в зелёный. Теперь, если вернуться к пересчету пар, поскольку клетка может делиться с двумя соседними клетками, каждая пара будет иметь своего соседа только снизу или справа.

Итак, у нас есть 135 клеток. Если бы каждая клетка была одного цвета в "зебровом" стиле, почти все клетки будут связаны. Тем самым, максимизация количества пар учитывает лишь индекс однородной раскраски.

В общем случае, Вова может гарантированно получить от 40 до 45 пар клеток в зелёный цвет. Это значит, что он может получить около 400 до 450 рублей за все перекрашенные клетки, но для наилучшего результата, предполагая, что мы максимально упростили каждый шаг, низший гарантированный уровень будет при одновременном чередовании всех цветов всё равно давать условные 40 пар, что означает:

200 рублей гарантированных для Вовы.