Решение задачи 221

Условие:

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

Решение:

Давайте запустим следующий процесс:

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

Затем проходим все столбцы слева направо и делаем то же самое.

За один такт этого процесса будем считать один проход всех строк и всех столбцов.

Что можно сказать про сумму чисел во всей таблице, когда мы меняем знаки у всех чисел в строке (столбце) с отрицательной суммой чисел? Конечно же она увеличивается. Отрицательная сумма в строке (столбце) меняется на положительную, сумма в остальных строках (столбцах) не меняется.

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

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

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