Задача комбинаторики на основе алгоритмов Стиль IMO [дубликат]

Question

Проблема описана на картинке, решение должно быть конструктивным доказательством, поэтому вам нужно найти алгоритм, который работает независимо от таких вещей, как время работы. Любая помощь будет рада, я не могу это решить, и я пытаюсь какое-то время

РЕДАКТИРОВАТЬ: Моим основным направлением было изменение знака на каждом необработанном с отрицательной суммой, теперь каждое сырье завершено, а сумма всех записей неотрицательна (поскольку сумма всех исходных данных теперь неотрицательна)

Answer 1

Если в какой-либо строке или столбце есть отрицательная сумма, выберите одну и поменяйте знаки местами.

Повторяйте процесс.

После каждого перехода сумма всех записей в матрице увеличивается.

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

Отсюда следует, что процесс в конечном итоге завершится.

Answer 2

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