Перестановка столбцов в таблице для неотрицательной диагональной суммы
В таблицу n×n записаны n² чисел, сумма которых неотрицательна. Докажите, что можно переставить столбцы таблицы так, что сумма n чисел по диагонали, идущей из левого нижнего угла в правый верхний, будет неотрицательна.
Разобрать решение
Назовем циклическим сдвигом такое преобразование таблицы: 1-й столбец переставляется на место 2-го, 2-й на место 3-го, ..., наконец последний, n-й – на место 1-го. Обозначим через s0 сумму чисел, стоящих на диагонали таблицы, через sk – сумму чисел, которые попадут на диагональ, если проделать циклический сдвиг k раз. Сумма s всех чисел в таблице равна s0 + s1 + ... + sn–1, потому что если проделать циклический сдвиг 0, 1, ..., n – 1 раз, то за это время каждое число в таблице побывает на диагонали ровно однажды.
По условию s неотрицательно, следовательно, некоторое sk должно быть неотрицательно. Проделав циклический сдвиг k раз, мы получим требуемую перестановку столбцов.
Обсуждение
0Комментариев пока нет.