|
|
 |
Условие
В клетки таблицы m×n вписаны некоторые числа. Разрешается одновременно менять знак у всех чисел некоторого столбца или некоторой строки. Доказать, что многократным повторением этой операции можно превратить данную таблицу в такую, у которой суммы чисел, стоящих в каждом столбце и каждой строке, неотрицательны.
Решение
С помощью перемен знака у чисел некоторого столбца или некоторой строки таблицы мы можем, очевидно, получить не больше чем 2mn, различных таблиц; (2mn — число способов выбора знаков у mn чисел). Поскольку таких таблиц имеется конечное число, среди них существует (может быть, не одна) таблица, сумма всех чисел которой максимальна. Если бы у этой таблицы сумма чисел некоторой строки была бы отрицательна, то путём перемены знака у всех чисел этой строки мы получили бы таблицу с большей общей суммой (так как суммы чисел, стоящих во всех остальных строках, при этом не меняются). По той же причине не может быть отрицательной сумма чисел никакого столбца таблицы. Итак, мы должны, меняя знаки у чисел некоторых строк и столбцов, прийти к таблице с наибольшей общей суммой – она и будет искомой.
Замечания
Можно доказать, что для таблицы m×n всегда можно обойтись не более чем m+n/2 операциями.
Источники и прецеденты использования
| журнал | |
| Название | "Квант" |
| год | |
| Год | 1971 |
| выпуск | |
| Номер | 4 |
| Задача | |
| Номер | М80 |
| олимпиада | |
| Название | Московская математическая олимпиада |
| год | |
| Номер | 24 |
| Год | 1961 |
| вариант | |
| 1 | |
| Класс | 10 |
| Тур | 2 |
| задача | |
| Номер | 3 |
| олимпиада | |
| Название | Московская математическая олимпиада |
| год | |
| Номер | 24 |
| Год | 1961 |
| вариант | |
| 1 | |
| Класс | 9 |
| Тур | 2 |
| задача | |
| Номер | 2 |
