16-я Международная Жаутыковская олимпиада по математике, 2020 год
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1.
Ответ. $3n^2-5n+2$.
Решение. Такая сумма получается, если закрасить в чёрный цвет все
строки с чётными номерами. Докажем, что она максимальна.
Очевидно, что указанная в условии сумма равна количеству
пар клеток с общей вершиной, в которых одна клетка черная, а другая белая.
Заметим, что пары таких клеток бывают двух типов: граничащие по стороне
и не граничащие. Посчитаем количество пар обоих типов другим способом.
Напишем во всех {\it узлах} доски нули, а затем для каждой пары второго типа
прибавим 1 к числу в узле, по которому граничат клетки этой пары (такой узел
ровно один). Для каждой пары первого типа прибавим по $1\over 2$
в каждый из двух узлов, по которым граничат клетки этой пары. Таким образом,
для каждой пары мы прибавили 1 к сумме всех чисел в узлах, значит, после
всех операций сумма чисел в узлах равна числу искомых пар клеток.
Разберемся, какие числа могут стоять в узлах. Несложный перебор показывает,
что:
(i) во внутреннем узле доски стоит число 3 тогда и только тогда, когда
там сходятся две соседние по стороне черные клетки и две соседние белые;
(ii) во всех остальных внутренних узлах числа не больше 2;
(iii) в граничном узле стоит ${1\over 2}$, если содержащие его клетки
разного цвета, и 0 в противном случае;
(iv) в углу всегда стоит 0.
{\it Замечание:} здесь уже доказано, что рассматриваемая сумма
не превосходит $3\times (n-1)^2 + {1\over 2}(4n-4)=3n^2-4n+1$.
Даже если вам не удалось доказать ничего больше -- такие оценки стоит писать.
Обозначим $S=3n^2-4n+1$.
Докажем, что числа во всех узлах не могут быть максимальными одновременно.
Точнее, докажем следующее.
{\bf Определение.} Число в узле {\it максимально}, если узел
внутренний и число равно 3, либо узел граничный и число равно $1\over 2$.
{\bf Определение.} {\it Путь} -- это последовательность узлов, в которой
любые два стоящих подряд узла отстоят друг от друга на сторону клетки.
{\bf Лемма.} При любой покраске доски на любом пути из узла на
горизонтальной стороне доски в узел на вертикальной стороне доски, не проходящем
через угловые клетки, есть число, не являющееся максимальным.
{\bf Доказательство.} Предположим противное. Тогда, если выбрать цвет одной
из клеток, содержащей узел на вертикальной стороне, раскраска остальных
клеток, примыкающих к пути (клетки содержащие узлы пути), определена однозначно, но в узле на горизонтальной
стороне стоит 0.
Докажем, что сумма чисел в любой раскраске не превосходит
суммы максимальных чисел, уменьшенной на четверть числа узлов, лежащих
на сторонах (но не в вершинах доски). Рассмотрим всевозможные квадраты с вершиной
в левом нижнем углу доски. Правая и верхняя стороны такого квадрата образуют
путь, удовлетворяющий условию леммы. Такой же набор путей порождают
квадраты с вершиной в правом верхнем углу доски. Каждый узел на стороне покрыт
ровно одним из полученных $2n-2$ путей, а каждый внутренний узел -- двумя.
Рассмотрим произвольную покраску доски. В соответствующем ей наборе чисел
в узлах на каждом пути есть число, меньше максимального (по Лемме).
Если это число на стороне, оно меньше максимального
на $1\over 2$ и не входит больше ни в какой путь. Если это число во внутреннем
узле, оно входит максимум в два пути и меньше максимального хотя бы
на 1. Таким образом, вклад каждого пути в сумму меньше максимального хотя бы
на $1\over 2$, ч. и т.д.
{\bf Интересный вопрос:} позволяют ли приведенные выше соображения подсчитать
число раскрасок с наибольшей суммой?
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.