16-я Международная Жаутыковская олимпиада по математике, 2020 год

На доске $n\times n$ ($n>2$) некоторые клетки чёрные, а остальные белые. В каждой белой клетке записано количество чёрных клеток, имеющих с ней хотя бы одну общую вершину. Найдите наибольшее возможное значение суммы всех записанных чисел. ( Н. Седракян )

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

Комментарии от администратора Комментарии от администратора №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 Интересный вопрос:} позволяют ли приведенные выше соображения подсчитать число раскрасок с наибольшей суммой?