Разделы 
Дополнительно
Задача по математике - 2887
2019-05-06 
Дана прямоугольная таблица размером $m \times n$, во все клетки которой вписаны некоторые числа. Разрешается одновременно менять знаки у всех чисел одной строки или у всех чисел одного столбца. Доказать, что, применяя эту операцию несколько раз, мы всегда можем прийти к таблице, у которой суммы чисел каждой строки и каждого столбца неотрицательны.
Решение:
Ясно, что если $a_{ij}$ - элемент таблицы, стоящий в ней на пересечении $i$-й строки и $j$-го столбца (где $i, j = 1, 2, \cdots$ или $m$, соответственно $n$), то во всех таблицах, получаемых из исходной «допустимыми» преобразованиями, на этом месте стоит либо число $n$ либо число - (ибо наши преобразования таблиц сводятся к переменам знаков некоторых из входящих в таблицу чисел). Поэтому общее число «допустимых» таблиц заведомо не превосходит $2^{mn}$, т.е. конечно. (Число $2^{mn}$ равно количеству всевозможных наборов $mn$ чисел $a_{ij}$, каждое из которых может иметь два значения.) Из конечности числа рассматриваемых таблиц следует, что среди них можно указать такую, для которой сумма всех входящих в нее чисел максимальна (или несколько таблиц с одной и той же суммой чисел, большей суммы чисел всех других допустимых таблиц). Но если в такой «максимальной» таблице сумма элементов какой-либо строки или какого-либо столбца отрицательна, то, поменяв знаки всех чисел этой строки или этого столбца, мы придем к новой «допустимой» таблице с большей суммой входящих в нее чисел; поэтому в «максимальной» таблице суммы всех элементов любой строки и любого столбца заведомо неотрицательны.
Дана прямоугольная таблица размером $m \times n$, во все клетки которой вписаны некоторые числа. Разрешается одновременно менять знаки у всех чисел одной строки или у всех чисел одного столбца. Доказать, что, применяя эту операцию несколько раз, мы всегда можем прийти к таблице, у которой суммы чисел каждой строки и каждого столбца неотрицательны.
Решение:
Ясно, что если $a_{ij}$ - элемент таблицы, стоящий в ней на пересечении $i$-й строки и $j$-го столбца (где $i, j = 1, 2, \cdots$ или $m$, соответственно $n$), то во всех таблицах, получаемых из исходной «допустимыми» преобразованиями, на этом месте стоит либо число $n$ либо число - (ибо наши преобразования таблиц сводятся к переменам знаков некоторых из входящих в таблицу чисел). Поэтому общее число «допустимых» таблиц заведомо не превосходит $2^{mn}$, т.е. конечно. (Число $2^{mn}$ равно количеству всевозможных наборов $mn$ чисел $a_{ij}$, каждое из которых может иметь два значения.) Из конечности числа рассматриваемых таблиц следует, что среди них можно указать такую, для которой сумма всех входящих в нее чисел максимальна (или несколько таблиц с одной и той же суммой чисел, большей суммы чисел всех других допустимых таблиц). Но если в такой «максимальной» таблице сумма элементов какой-либо строки или какого-либо столбца отрицательна, то, поменяв знаки всех чисел этой строки или этого столбца, мы придем к новой «допустимой» таблице с большей суммой входящих в нее чисел; поэтому в «максимальной» таблице суммы всех элементов любой строки и любого столбца заведомо неотрицательны.
