Задача 34901

Тема:    [ Подсчет двумя способами ]

Сложность: 2+ Классы:

Условие

В таблицу n*n записаны n² чисел, сумма которых неотрицательна. Докажите, что можно переставить столбцы таблицы так, что сумма n чисел, расположенных по диагонали, идущей из левого нижнего угла в правый верхний, будет неотрицательна.

Подсказка

Рассмотрите циклические сдвиги столбцов.

Решение

Назовем циклическим сдвигом такое преобразование таблицы: первый столбец переставляется на место второго, второй - на место третьего, и т.д., наконец, последний - на место первого. Обозначим через s₀ сумму чисел, стоящих на диагонали таблицы, через s₁ сумму чисел, которые попадут на диагональ после циклического сдвига, и вообще, через s_k сумму чисел, которые попадут на диагональ, если проделать циклический сдвиг k раз. Ясно, что сумма всех чисел в таблице равна s=s₀+s₁+...+s_n-1, потому что если проделать циклический сдвиг 0,1,...,n-1 раз, то за это время каждое число побывает на диагонали ровно однажды. По условию s неотрицательно, следовательно, некоторое s_k неотрицательно. Проделав циклический сдвиг k раз, мы получим требуемую перестановку столбцов.

Источники и прецеденты использования

web-сайт

задача