Олимпиадная задача по алгебраическим методам: перестановка столбцов в
Задача
В таблицу n*n записаны n2чисел, сумма которых неотрицательна. Докажите, что можно переставить столбцы таблицы так, что сумма n чисел, расположенных по диагонали, идущей из левого нижнего угла в правый верхний, будет неотрицательна.
Решение
Назовем циклическим сдвигом такое преобразование таблицы: первый столбец переставляется на место второго, второй - на место третьего, и т.д., наконец, последний - на место первого. Обозначим через s0сумму чисел, стоящих на диагонали таблицы, через s1сумму чисел, которые попадут на диагональ после циклического сдвига, и вообще, через skсумму чисел, которые попадут на диагональ, если проделать циклический сдвиг k раз. Ясно, что сумма всех чисел в таблице равна s=s0+s1+...+sn-1, потому что если проделать циклический сдвиг 0,1,...,n-1 раз, то за это время каждое число побывает на диагонали ровно однажды. По условию s неотрицательно, следовательно, некоторое skнеотрицательно. Проделав циклический сдвиг k раз, мы получим требуемую перестановку столбцов.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь