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

Дано натуральное число $n\geqslant 2$. У Элвина есть таблица $n\times n$, заполненная вещественными числами (в каждой клетке записано ровно одно число). Назовём ладейным множеством множество из $n$ клеток, расположенных как в $n$ различных столбцах, так и в $n$ различных строках. Предположим, что сумма чисел в клетках любого ладейного множества неотрицательна.
   За ход Элвин выбирает строку, столбец, а также вещественное число $a$; к каждому числу в выбранной строке он прибавляет $a$, а из каждого числа в выбранном столбце — вычитает $a$ (таким образом, число в пересечении строки и столбца не изменяется). Докажите, что Элвин может, сделав несколько ходов, добиться, чтобы все числа в таблице стали неотрицательными. ( И. Богданов )

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

Для начала докажем, что можно уменьшить некоторые числа в таблице так, что в каждом ладейном множестве сумма равна 0. Запустим процесс, в течение которого мы находим число в таблице, для которого все ладейные множества содержащие его положительны, и уменьшим его так, что какое то ладейное множество будет иметь сумму 0, а остальные останутся неотрицательными. Так как количество множеств, которые могут иметь сумму 0 ограничено, а также возрастает хотя бы на один с каждой такой операцией, то рано или поздно процесс остановится. В этот момент рассмотрим какое то ладейное множество с положительной суммой, для каждого из чисел входящих в это ладейное множество мы можем выбрать другое ладейное множество содержащее его с суммой 0. Сделаем это для каждого числа в этом множестве, некоторые клетки при этом могут быть выбраны несколько раз. Рассмотрим двудольный граф $G$, вершины первой доли которого соответствуют столбцам, а строки вершинам второй доли, и будем проводить ребро в этом графе только если клетка стоящая на пересечении этого столбца и строки содержится в нашей выборке (в графе могут быть кратные ребра). Тогда несложно понять, что степень каждой вершины равна $n$. Уберем теперь из этого графа все ребра, которые соответствуют изначальному множеству вершин. Останется граф, в котором степень каждой вершины равна $n-1$, то есть граф останется "регулярным". Известно, что ребра двудольного регулярного графа можно поделить на совершенные паросочетания (по Лемме Холла). Но мы знаем, что каждое паросочетание соответствует ладейному множеству, то есть общая сумма в нашей выборке должна быть положительной (потому что все ладейные неотрицательные и мы убрали ладейное множество с положительной суммой), с другой стороны это была выборка из ладейных множеств с суммой 0, откуда получаем противоречие. Значит в конце этого процесса во всех ладейных множествах сумма 0.

Теперь докажем, что если сумма во всех ладейных множествах равна 0, то мы можем сделать все числа нулями. Пронумеруем столбцы слева направо и строки сверху вниз. Во первых, несложно проверить, что ладейные суммы не меняются при данной операции (♥). Во вторых, если рассмотреть две пары чисел, которые образуют вершины прямоугольника в этой таблице, то их суммы равны, потому что равны суммы соответствующих ладейных множеств, которые отличаются только этими двумя парами ($\star$). Несложно сделать первый столбец нулями, просто применяя операцию к числам второго столбца, каждый раз отнимая в строке то число, которое стоит в соответствующем пересечении этой строки и первого столбца. После этого, по $\star$ числа в одном столбце одинаковые. После этого будем выполнять такой алгоритм: Берем первый столбец (если это не $n$-й) все числа которого одинаковы и не равны 0 - пусть равны $a$ и пусть номер столбца $i$. Берем его число в последней строке и применяем операцию к нему так, чтобы во всех строках этого столбца кроме последней были 0, а в последней строке первые $i$ чисел были равны $a$. После этого применяем операцию к числу в $n$-ом столбце $n$-ой строки так, чтобы в первых $i$ столбцах были 0. В конце этого алгоритма в первых $n-1$ столбцах будут нули, но тогда по ♥ числа в последнем столбце тоже нули, потому что для каждого числа оттуда можно выбрать ладейное множество, которое содержит его, и так как все остальные числа в этом ладейном множестве 0 и сумма тоже 0, то и последнее число должно быть нулем.

То есть мы, уменьшив предварительно некоторые числа, добились того, что все числа 0, а значит до уменьшения все числа неотрицательные, что и требовалось.