Question

428. В клетки прямоугольной таблицы вписаны некоторые числа. Разрешено одновременно менять знак у всех чисел некоторогостолбца или некоторой строки. Докажите, что этими опера-циями можно превратить данную таблицу в такую, у которойсуммы чисел, стоящих в любом столбце или в любой строке,неотрицательны.​

Answer 1

Ответ:

С помощью перемен знака у чисел некоторого столбца или некоторой строки таблицы мы можем, очевидно, получить не больше чем 2ab, различных таблиц. Поскольку таких таблиц имеется конечное число, среди них существует таблица, сумма всех чисел которой максимальна.

Мы должны, меняя знаки у чисел некоторых строк и столбцов, прийти к таблице с наибольшей общей суммой - она и будет искомой.

Answer 2

Для доказательства того, что данную таблицу можно превратить в такую, у которой суммы чисел в любом столбце или строке неотрицательны, мы можем использовать метод математической индукции.

Базовый шаг:

Рассмотрим таблицу размером 1x1, то есть таблицу, состоящую из одной ячейки. В этом случае сумма чисел в столбце или строке будет равна самому числу в ячейке. Если это число неотрицательное, то условие уже выполняется. Если же число отрицательное, мы можем просто изменить его знак, применив операцию к этой единственной ячейке. Таким образом, базовый шаг выполнен.

Шаг индукции:

Предположим, что для таблиц размером k x k условие выполняется, то есть мы можем превратить таблицу так, чтобы суммы чисел в любом столбце или строке были неотрицательными.

Рассмотрим таблицу размером (k+1) x (k+1). Мы можем разделить эту таблицу на две части: верхнюю часть размером k x (k+1) и нижнюю часть размером 1 x (k+1). По предположению индукции, мы можем превратить верхнюю часть таблицы так, чтобы суммы чисел в любом столбце или строке были неотрицательными.

Теперь рассмотрим нижнюю часть таблицы. Если сумма чисел в нижней части таблицы уже неотрицательна, то условие выполняется для всей таблицы.

Если же сумма чисел в нижней части таблицы отрицательна, мы можем применить операцию изменения знака ко всем числам в нижней части таблицы. После этого сумма чисел в нижней части таблицы станет неотрицательной.

Теперь объединим верхнюю и нижнюю части таблицы. Суммы чисел в столбцах и строках, которые пересекаются с нижней частью таблицы, не изменились, так как мы просто поменяли знаки чисел в нижней части. Следовательно, суммы чисел в любом столбце или строке всей таблицы стали неотрицательными.

Таким образом, по принципу математической индукции мы доказали, что данную таблицу можно превратить в такую, у которой суммы чисел в любом столбце или строке неотрицательны.